008、相交链表

0、题目描述

相交链表

1、法1

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* pa = headA;
    struct ListNode* pb = headB;
    while (pa)
    {
        pb = headB;
        while (pb)
        {
            if (pa == pb)
            {
                return pa;
            }
            pb = pb->next;
        }
        pa = pa->next;
    }
    return NULL;
}

2、法2

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    int lenA = 1;   int lenB = 1;
    struct ListNode* curA = headA;    
    struct ListNode* curB = headB;
    while (curA->next)
    {
        curA = curA->next;
        lenA++;
    }
    while (curB->next)
    {
        curB = curB->next;
        lenB++;
    }
    
    if (curA != curB)
        return NULL;
    else
    {
    	//注意这里的条件LenA > lenB必须一样，在一样的条件下做出不一样的选择。
        struct ListNode* LongList = lenA > lenB ? headA : headB;
        struct ListNode* ShortList = lenA > lenB ? headB : headA;
        //abs是求绝对值的宏，这里的gap代表长度差
        int gap = abs(lenA - lenB);
        while (gap--)
        {
            LongList = LongList->next;
        }
        //
        while (LongList->next)
        {
            if (LongList == ShortList)
                break;
            LongList = LongList->next;
            ShortList = ShortList->next;
        }
        return LongList;
    }
}