最直接法
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
|
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set<ListNode*> set;
while(headA)
{
set.insert(headA);
headA = headA->next;
}
while(headB)
{
if(set.find(headB) != set.end())
return headB;
headB = headB->next;
}
return nullptr;
}
};
|
预先求差
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA{ 0 };
int lenB{ 0 };
ListNode* a = headA;
ListNode* b = headB;
while(a)
{
++lenA;
a = a->next;
}
while(b)
{
++lenB;
b = b->next;
}
if(lenA < lenB)
{
for(int i = 0; i < lenB - lenA; ++i)
headB = headB->next;
}else
{
for(int i = 0; i < lenA - lenB; ++i)
headA = headA->next;
}
while(headA && headB)
{
if(headA == headB)
return headA;
headA = headA->next;
headB = headB->next;
}
return nullptr;
}
};
|
2次迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *a = headA;
ListNode *b = headB;
while(a != b)
{
a = a == nullptr ? headB : a->next;
b = b == nullptr ? headA : b->next;
}
return a;
}
};
|
他们第一次跑会有一个长度的差，短的先跑到终点后，到长的端点。当长的指针跑到终点后，回到短的端点。此时先前一个刚好跑了他们的距离差，这是他们在距离上是处于同一个起点的。
设短的到交点距离x，长的到交点距离y，公共部分距离为z，则如果要求交点，那么让他们走到交点的路程一致即可，则让短的走到头后跳到长，长的走到头后跳到短，最后对于短头来说x+y+z,长头也是x+y+z，刚好在交点相交。
review
如果没交点，第二轮时候他们肯定一同走到尾巴。长的比短的多出来的步数，由于短的先走到头，然后比长的走到短头会刚好多走这么几步，于是就处于同意起跑线。
具体见discussion中的评论第一条