[Leetcode 160] 相交链表

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定两个单链表的头节点 headA 和 headB,返回两个单链表相交的起始节点。
notion image
图中两个链表在节点 c1 开始相交
如果两个链表不存在相交节点,返回 null 。
 
提示:
链表必须保持其原始结构 。
题目保证整个链式结构中不存在环。
 
示例 1:
notion image
示例 2:
notion image
示例 3:
notion image

解法一:两次遍历

这个解法思路非常直接:
  • 我们先走一遍链表 A,把 A 里的每个节点指针都丢进一个 set 里;
  • 然后再走一遍链表 B,每到一个节点,就看一下这个节点是不是已经在 set 里面:
    • 如果在,说明这个节点就是两个链表的第一个公共节点,直接返回;
    • 如果都走到底还是没遇到,那就是不相交,返回 None
这个解法的优点就是简单,很符合直觉;缺点是要用一个额外的集合来存所有节点指针,空间是 O(m+n)
复杂度:
  • 时间:O(m + n),各走一遍;
  • 空间:O(m + n)。

解法二:长度对齐

链表 A 长度为 m,链表 B 长度为 n
如果有相交,那么从交点到结尾这一段(c)是共享的;
  • A 从头走到交点,走了 m - c 步;
  • B 从头走到交点,走了 n - c 步;
如果让长的那条链先“多走几步”(如果 A 更长):
  • A 先走 m - n
  • 然后 B 再出发
  • 再一起同步走
    • 如果有交点,就会在第一次经过该节点时相遇;
    • 如果没有交点,会同时走到 None
复杂度
  • 时间:O(m + n)
  • 空间:O(1)。

解法三:双指针(推荐)

把链表 A 和链表 B 想成两条不同长度的道路,如果它们有交点,那交点后面的那段道路是完全共享的。 问题在于两条链表长度不一样,直接同步往前走,会造成“有一条先走到底”。
如何让两个指针在某一个时刻到达同一个节点呢?
让它们把彼此的整条路都走一遍。 指针 P: 先走完 A,再走 B; 指针 Q:先走完 B,再走 A。
如果有交点,P和Q在经过第二次交点时,必然会在同一个时刻相遇;
如果没有交点,最后就会都停在None上。
例子1:
notion image
P: 4 → 1 → 8 → 4 → 5 → null → 5 → 6 → 1 → 8
Q: 5 → 6 → 1 → 8 → 4 → 5 → null → 4 → 1 → 8
复杂度
  • 时间:O(m + n),每个指针最多把两条链表各走一遍;
  • 空间:O(1),只用了两个指针变量。
上一篇
[Leetcode 146] LRU 缓存
下一篇
[Leetcode 171] Excel 列名转换为数字