剑指 Offer 52. 两个链表的第一个公共节点

一道easy难度的题目，但是很好的考察了双指针的思想以及链表的知识，值得反复练习。

1.笨方法（暴力！）

时间复杂度 O(n²)

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // int skipA = 0, skipB = 0;
        for(ListNode *p = headA; p; p = p->next){
            for(ListNode *q = headB; q; q = q->next){
                if(p == q) return p;
            }
        }
        return NULL;
    }
};

2. 双指针思想

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p = headA, *q = headB;
        while(p != q){
            p = p ? p->next : headB;
            q = q ? q->next : headA;
        }
        
        return p;
    }
};

两个指针p, q，分别从两个链表的头节点开始向后移动，若达到链表末端，则从另一个链表的头节点向后移动，直到两个指针相等。

我的理解：首先分为两种情况，即两个链表是否存在公共部分。

a )不存在公共部分。这里设两个链表长度分别为l1和l2。两个指针会同时走完两个链表，p指针先走完l1，再走完l2，q指针先走完l2，再走完l1，路程均为l1+l2。最后p和q都指向链表末端的NULL，循环结束。

b )存在公共部分。我们可以沿用a情况的结论，设两个链表非公共部分的长度分别为l1和l2，公共部分长度为c，则在第一个链表中，c位于l1之后，第一个链表的长度为l1+c，同理第二个链表长度为l2+c。这样，循环结束时p指针和q指针会同时指向l1和l2之后的第一个节点，也就是c的头节点！