### 题目

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. Credits: Special thanks to @stellari for adding this problem and creating all test cases.

### 用HashSet记录listA的所有节点

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$

#### 代码

public class Solution {
if (headA == null || headB == null) { return null; }
Set<ListNode> memo = new HashSet<>();
while (cur != null) {
cur = cur.next;
}
while (cur != null) {
if (memo.contains(cur)) { return cur; }
cur = cur.next;
}
return null;
}
}


### 计算listA和listB的长度

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


#### 代码

public class Solution {
if (headA == null || headB == null) { return null; }
// curA,curB归同一起跑线
while (sizeA > sizeB) {
curA = curA.next;
sizeA--;
}
while (sizeB > sizeA) {
curB = curB.next;
sizeB--;
}
while (curA != curB && curA != null) {
curA = curA.next;
curB = curB.next;
}
return (curA == null)? null : curA;
}
public int size(ListNode list) {
ListNode cur = list;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
}


#### 有个小诀窍，可以不计算长度

listA先跑到c3结尾处，跳转到listB的开头b1接着跑。listB后跑到c3结尾处，跳转到listA的开头a1接着跑。如果listAlistB相交，则会在第二圈同时到达c1。如果不想交，会同时跑到null

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


#### 代码

public class Solution {
if (headA == null || headB == null) { return null; }
while (curA != curB) { // will stop after seconde iteration if no intersection exists
curA = (curA == null)? headB : curA.next;
curB = (curB == null)? headA : curB.next;
}
return curA;
}
}


### Walker和Runner的追逐算法

#### Walker和Runner追逐算法细节如下

• 从起始节点到cycle的首个节点之间的距离是s步。
• 从cycle的首个节点到walkerrunner相遇的节点之间的距离为m步。
• cycle的周长为r步。

2k - k = nr (1式)（runner在遇到walker之前，已经绕着cycle跑了n圈了）

k = s + m (2式)（就是walker从起始点跑到和runner相遇的地方的距离，可以肯定walker没有跑完一圈）

s = nr - m (3式)

#### 代码

public class Solution {
if (headA == null || headB == null) { return null; }
while (end != null && end.next != null) { // cur stop at the last node
end = end.next;
}
end.next = headA; // make a circle
while (runner != null && runner.next != null) {
walker = walker.next;
runner = runner.next.next;
if (runner == walker) { // find circle
while (anotherWalker != walker) { // BLACK MAGIC
anotherWalker = anotherWalker.next;
walker = walker.next;
}
end.next = null;
return walker;
}
}
end.next = null;
return null;
}
}