某教练同时带教两位学员，分别以链表 l1、l2 记录了两套核心肌群训练计划，节点值为训练项目编号。两套计划仅有前半部分热身项目不同，后续正式训练项目相同。请设计一个程序找出并返回第一个正式训练项目编号。如果两个链表不存在相交节点，返回 null 。

此题是寻找链表公共结点，设公共部分长c，单独的部分分别为a，b

首先想到的是先同时遍历两个链表，当短的一方遍历结束时（共a+c），另一方也遍历了（a+c），另一方还需要遍历（b-a），而从头遍历的话A需要遍历a，B需要遍历b

再次从头遍历B，当b-a遍历结束时，还需遍历（a）即可到达公共结点，此距离与从头遍历A的距离相等，

所以此时同时开始遍历A，两节点在遍历过程中一定会相交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL)
            return NULL;
        ListNode *i = headA, *j = headB;
        while (i != NULL && j != NULL) {
            i = i->next;
            j = j->next;
        }
        if (i == NULL) {
            i = headB;
        }
        if (j == NULL) {
            j = headA;
        }
        while (i != NULL && j != NULL) {
            i = i->next;
            j = j->next;
        }
        if (i == NULL) {
            i = headB;
        }
        if (j == NULL) {
            j = headA;
        }
        while (i != NULL && j != NULL && i != j) {
            i = i->next;
            j = j->next;
        }
        return i;
    }
};

总的来说两节点遍历的距离都是a+b+c，速度一样，两指针一定同时到达终点

我们可以把遍历过程分为三段，每段路程分别为a，b，c，当 i 跑完a+c时我们将他放到b继续跑

对于 j 同理，二者最后一定同时到达交点（无交点时可以假设NULL为交点）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *i = headA, *j = headB;
        while (i != j) {
            i = i == NULL ? headB : i->next;
            j = j == NULL ? headA : j->next;
        }
        return i;
    }
};