Links

0160. 相交链表

题目地址(160. 相交链表)

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

题目描述

编写一个程序,找到两个单链表相交的起始节点。

前置知识

  • 链表
  • 双指针

解法一: 哈希法

有 A, B 这两条链表, 先遍历其中一个,比如 A 链表, 并将 A 中的所有节点存入哈希表。
遍历 B 链表,检查节点是否在哈希表中, 第一个存在的就是相交节点
  • 伪代码
data = new Set() // 存放A链表的所有节点的地址
while A不为空{
哈希表中添加A链表当前节点
A指针向后移动
}
while B不为空{
if 如果哈希表中含有B链表当前节点
return B
B指针向后移动
}
return null // 两条链表没有相交点
  • 代码支持: JS
JS Code:
let data = new Set();
while (A !== null) {
data.add(A);
A = A.next;
}
while (B !== null) {
if (data.has(B)) return B;
B = B.next;
}
return null;
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$

解法二:双指针

  • 例如使用 a, b 两个指针分别指向 A, B 这两条链表, 两个指针相同的速度向后移动,
  • 当 a 到达链表的尾部时,重定位到链表 B 的头结点
  • 当 b 到达链表的尾部时,重定位到链表 A 的头结点。
  • a, b 指针相遇的点为相交的起始节点,否则没有相交点
(图 5)
为什么 a, b 指针相遇的点一定是相交的起始节点? 我们证明一下:
  1. 1.
    将两条链表按相交的起始节点继续截断,链表 1 为: A + C,链表 2 为: B + C
  2. 2.
    当 a 指针将链表 1 遍历完后,重定位到链表 B 的头结点,然后继续遍历直至相交点(a 指针遍历的距离为 A + C + B)
  3. 3.
    同理 b 指针遍历的距离为 B + C + A
  • 伪代码
a = headA
b = headB
while a,b指针不相等时 {
if a指针为空时
a指针重定位到链表 B的头结点
else
a指针向后移动一位
if b指针为空时
b指针重定位到链表 A的头结点
else
b指针向后移动一位
}
return a
  • 代码支持: JS, Python, Go, PHP
JS Code:
var getIntersectionNode = function (headA, headB) {
let a = headA,
b = headB;
while (a != b) {
a = a === null ? headB : a.next;
b = b === null ? headA : b.next;
}
return a;
};
Python Code:
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
a, b = headA, headB
while a != b:
a = a.next if a else headB
b = b.next if b else headA
return a
Go Code:
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
// a=A(a单独部分)+C(a相交部分); b=B(b单独部分)+C(b相交部分)
// a+b=b+a=A+C+B+C=B+C+A+C
a := headA
b := headB
for a != b {
if a == nil {
a = headB
} else {
a = a.Next
}
if b == nil {
b = headA
} else {
b = b.Next
}
}
return a
}
PHP Code:
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val) { $this->val = $val; }
* }
*/
class Solution
{
/**
* @param ListNode $headA
* @param ListNode $headB
* @return ListNode
*/
function getIntersectionNode($headA, $headB)
{
$a = $headA;
$b = $headB;
while ($a !== $b) { // 注意, 这里要用 !==
$a = $a ? $a->next : $headB;
$b = $b ? $b->next : $headA;
}
return $a;
}
}
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$