题目来源
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.

一道求交叉点的题目，是道简单题。我一开始的想法是，先从A开始遍历到末尾，记下长度l1，B遍历到末尾记下长度l2，谁长谁先遍历abs(l1-l2)长度，然后两者一起遍历，当两个指针指向同一个节点时，就是所求的交叉节点。然后就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;
    }
};

然后看看大神们的做法，感到害怕，又简洁又快。相当于是把A和B接起来，B和A接起来，然后两个指针同时遍历，到两个指针指向同一个节点时，那个节点就是交叉节点。
差不多就是下图那样：

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;
    }
};