0160. 相交链表
题目地址(160. 相交链表)
题目描述
1
编写一个程序，找到两个单链表相交的起始节点。
Copied!
前置知识
- 链表
- 双指针
解法一: 哈希法
有 A, B 这两条链表, 先遍历其中一个，比如 A 链表, 并将 A 中的所有节点存入哈希表。
遍历 B 链表,检查节点是否在哈希表中, 第一个存在的就是相交节点
- 伪代码
1
data = new Set() // 存放A链表的所有节点的地址
2
3
while A不为空{
4
哈希表中添加A链表当前节点
5
A指针向后移动
6
}
7
8
while B不为空{
9
if 如果哈希表中含有B链表当前节点
10
return B
11
B指针向后移动
12
}
13
14
return null // 两条链表没有相交点
Copied!
- 代码支持: JS
JS Code:
1
let data = new Set();
2
while (A !== null) {
3
data.add(A);
4
A = A.next;
5
}
6
while (B !== null) {
7
if (data.has(B)) return B;
8
B = B.next;
9
}
10
return null;
Copied!
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
解法二：双指针
- 例如使用 a, b 两个指针分别指向 A, B 这两条链表, 两个指针相同的速度向后移动,
- 当 a 到达链表的尾部时,重定位到链表 B 的头结点
- 当 b 到达链表的尾部时,重定位到链表 A 的头结点。
- a, b 指针相遇的点为相交的起始节点，否则没有相交点
（图 5）
为什么 a, b 指针相遇的点一定是相交的起始节点? 我们证明一下：
- 1.将两条链表按相交的起始节点继续截断，链表 1 为: A + C，链表 2 为: B + C
- 2.当 a 指针将链表 1 遍历完后,重定位到链表 B 的头结点,然后继续遍历直至相交点(a 指针遍历的距离为 A + C + B)
- 3.同理 b 指针遍历的距离为 B + C + A
- 4.伪代码
1
a = headA
2
b = headB
3
while a,b指针不相等时 {
4
if a指针为空时
5
a指针重定位到链表 B的头结点
6
else
7
a指针向后移动一位
8
if b指针为空时
9
b指针重定位到链表 A的头结点
10
else
11
b指针向后移动一位
12
}
13
return a
Copied!
- 代码支持: JS, Python, Go, PHP
JS Code:
1
var getIntersectionNode = function (headA, headB) {
2
let a = headA,
3
b = headB;
4
while (a != b) {
5
a = a === null ? headB : a.next;
6
b = b === null ? headA : b.next;
7
}
8
return a;
9
};
Copied!
Python Code：
1
class Solution:
2
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
3
a, b = headA, headB
4
while a != b:
5
a = a.next if a else headB
6
b = b.next if b else headA
7
return a
Copied!
Go Code:
1
/**
2
* Definition for singly-linked list.
3
* type ListNode struct {
4
* Val int
5
* Next *ListNode
6
* }
7
*/
8
func getIntersectionNode(headA, headB *ListNode) *ListNode {
9
// a=A(a单独部分)+C(a相交部分); b=B(b单独部分)+C(b相交部分)
10
// a+b=b+a=A+C+B+C=B+C+A+C
11
a := headA
12
b := headB
13
for a != b {
14
if a == nil {
15
a = headB
16
} else {
17
a = a.Next
18
}
19
if b == nil {
20
b = headA
21
} else {
22
b = b.Next
23
}
24
}
25
return a
26
}
Copied!
PHP Code:
1
/**
2
* Definition for a singly-linked list.
3
* class ListNode {
4
* public $val = 0;
5
* public $next = null;
6
* function __construct($val) { $this->val = $val; }
7
* }
8
*/
9
class Solution
10
{
11
/**
12
* @param ListNode $headA
13
* @param ListNode $headB
14
* @return ListNode
15
*/
16
function getIntersectionNode($headA, $headB)
17
{
18
$a = $headA;
19
$b = $headB;
20
while ($a !== $b) { // 注意, 这里要用 !==
21
$a = $a ? $a->next : $headB;
22
$b = $b ? $b->next : $headA;
23
}
24
return $a;
25
}
26
}
Copied!
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(1)$
最近更新 1yr ago