题目链接：Intersection of Two Linked Lists
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.
这道题的要求是找出两个链表的交叉点。如果没有交叉，返回null；要保持链表的原有结构；链表中没有环；要达到O(n)时间复杂度，O(1)空间复杂度。
最直接方式，对第一个链表的每个节点，遍历第二个链表，判断是否相等，如果相等，直接返回。不过这样时间复杂度为O(n^2)。
可以考虑用Hash表将第一个链表的所有节点存储起来，然后遍历第二个链表，查看每个节点是否在Hash表中。不过这样空间复杂度为O(n)。
那么接下来的方法，实现了O(n)时间复杂度，O(1)空间复杂度。
-
Plan A
如果两个链表相交，那么形状将会是“Y”字形。比如：
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
接下来，将A链表的尾节点的next指针指向B链表的头节点：
A: a1 → a2
↘
c1 → c2 → c3
↗ ↙
b3 ← b2 ← b1 :B
可以注意到，A、B链表共同形成一个环，A、B链表的交叉点就是开始出现环的位置。因此，可以利用Linked List Cycle II寻找环入口的思路即可。
不过需要注意一个问题，就是要保持链表的原有结构，因此将A、B两个链表连接后还需要拆开才行。
时间复杂度：O(n)（n为两个链表长度之和）
空间复杂度：O(1)
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
class Solution
{
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
if(headA == NULL || headB == NULL)
return NULL;
// 找到A链表的尾节点
ListNode *p = headA;
while(p -> next != NULL)
p = p -> next;
// 连接到B链表
p -> next = headB;
// 找到开始出现环的位置
ListNode *res = detectCycle(headA);
// 拆开两个链表
p -> next = NULL;
return res;
}
private:
ListNode *detectCycle(ListNode *head)
{
if(head == NULL || head -> next == NULL)
return NULL;
ListNode *s = head, *f = head;
while(f != NULL && f -> next != NULL)
{
s = s -> next;
f = f -> next -> next;
if(f == s)
{
s = head;
while(f != s)
{
s = s -> next;
f = f -> next;
}
return f;
}
}
return NULL;
}
};
-
Plan B
如果两个链表相交，那么两个链表从交点开始，后面的节点都是相同的。不过前面的并不相同，有可能A链表长，有可能B链表长，不过如有要是一样长就好了，这样就可以两个指针分布在两个链表上从前往后，一步一步地走即可。
因此，可以先求链表长度，令长的链表先走几步，这样两个链表再同时走，遇到相同的节点，就是交叉的位置了。
时间复杂度：O(n)（n为两个链表长度之和）
空间复杂度：O(1)
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
class Solution
{
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
if(headA == NULL || headB == NULL)
return NULL;
// 计算两个链表长度
int la = getLength(headA);
int lb = getLength(headB);
// 令长的链表先走出多出来的长度
ListNode *pa = la > lb ? forward(headA, la - lb) : headA;
ListNode *pb = lb > la ? forward(headB, lb - la) : headB;
// 两个链表上的指针同时前进，直到相等
while(pa != pb)
{
pa = pa -> next;
pb = pb -> next;
}
return pa;
}
private:
int getLength(ListNode *p)
{
int l = 0;
for( ; p != NULL; p = p -> next)
++ l;
return l;
}
ListNode *forward(ListNode *p, int n)
{
while(n -- && p != NULL)
p = p -> next;
return p;
}
};
-
Plan C
两个指针分布指向两个链表的头节点，每次每个指针各走一步。当指针走到链表尾的时候，就接着另一个链表开始走，这样直到两个指针相同，此时即为交叉点。
至于为什么？可以注意到每个链表上的指针所走的距离都是自身链表长度加上另一个链表上交点之前的长度，因此两个链表走的距离是相等的。比如：
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
两个链表上的指针行走路线为：
A: a1 -> a2 -> c1 -> c2 -> c3 -> b1 -> b2 -> b3 -> c1
B: b1 -> b2 -> b3 -> c1 -> c2 -> c3 -> a1 -> a2 -> c1
因此两个指针会相遇。可以看到，这样的思路，写出来的代码比较简短。。。
时间复杂度：O(n)（n为两个链表长度之和）
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution
{
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
if(headA == NULL || headB == NULL)
return NULL;
ListNode *pa = headA, *pb = headB;
while(pa != pb)
{
pa = pa == NULL ? headB : pa -> next;
pb = pb == NULL ? headA : pb -> next;
}
return pa;
}
};