題目來源
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

一道求交叉點(diǎn)的題目，是道簡(jiǎn)單題。我一開始的想法是，先從A開始遍歷到末尾，記下長度l1，B遍歷到末尾記下長度l2，誰長誰先遍歷abs(l1-l2)長度，然后兩者一起遍歷，當(dāng)兩個(gè)指針指向同一個(gè)節(jié)點(diǎn)時(shí)，就是所求的交叉節(jié)點(diǎn)。然后就AC了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int l1 = 0, l2 = 0;
        ListNode *cur1 = headA, *cur2 = headB;
        while (cur1) {
            l1++;
            cur1 = cur1->next;
        }
        while (cur2) {
            l2++;
            cur2 = cur2->next;
        }
        cur1 = headA, cur2 = headB;
        if (l1 >= l2) {
            for (int i=0; i<l1-l2; i++)
                cur1 = cur1->next;
        }
        else
            for (int i=0; i<l2-l1; i++)
                cur2 = cur2->next;
        while (cur1 && cur2) {
            if (cur1 == cur2)
                return cur1;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return NULL;
    }
};

然后看看大神們的做法，感到害怕，又簡(jiǎn)潔又快。相當(dāng)于是把A和B接起來，B和A接起來，然后兩個(gè)指針同時(shí)遍歷，到兩個(gè)指針指向同一個(gè)節(jié)點(diǎn)時(shí)，那個(gè)節(jié)點(diǎn)就是交叉節(jié)點(diǎn)。
差不多就是下圖那樣：

C:    b1 → b2 → b3 → c1 → c1 → c3 → a1 → a2
                                           ↘
                                            c1 → c2 → c3
                                           ↗            
D:    a1 → a2 → c1 → c1 → c3 → b1 → b2 → b3

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int l1 = 0, l2 = 0;
        ListNode *p1 = headA, *p2 = headB;
        while (p1 && p2) {
            if (p1 == p2) {
                return p1;
            }
            p1 = p1->next;
            p2 = p2->next;
            if (p1 == NULL)
                p1 = headB;
            else if (p2 == NULL)
                p2 = headA;
        }
        return NULL;
    }
};