🧩 Week 1 · Day 5 — LeetCode Hot 100 链表进阶篇
1️⃣ 相交链表
🧠 题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个链表 相交的起始节点。
如果两个链表不存在相交节点，返回 null。
题目保证整个链式结构中 不存在环。
💡 思路解析：双指针拼接法
核心思想是：
将两个链表「首尾相连」进行遍历，指针在两个链表上交替前进，最终会在相交点相遇；
若无相交节点，则同时到达 None。
假设：
-
链表 A 长度为
a + c -
链表 B 长度为
b + c -
c为公共部分长度
当两个指针分别走完两条链表（共 a + b + c 步）后：
-
若存在相交，则相遇于交点；
-
若不存在相交，则同时为
None。
🧾 代码实现
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
p, q = headA, headB
while p is not q:
p = p.next if p else headB
q = q.next if q else headA
return p
⚙️ 时间与空间复杂度
-
时间复杂度：O(n + m)
-
空间复杂度：O(1)
2️⃣ 环形链表 II
🧠 题目描述
给定一个链表的头节点 head，返回链表开始入环的第一个节点。
若链表中无环，则返回 None。
不允许修改 链表结构。
💡 思路解析：快慢指针（Floyd 判圈算法）
-
第一阶段：判断是否存在环
-
使用
slow每次走一步，fast每次走两步； -
若
fast == slow，说明链表中存在环。
-
-
第二阶段：找到入环点
-
设从头节点到入环点的距离为
a； -
从入环点到相遇点的距离为
b； -
环的长度为
c； -
则有：
fast = 2 * slow→2(a + b) = a + b + kc→ a = kc - b。 -
所以当
slow从相遇点出发，head从头出发，二者每次走一步，必定在入环点相遇。
-
🧾 代码实现
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast is slow: # 相遇，存在环
while slow is not head: # 再走 a 步，相遇点即入环口
slow = slow.next
head = head.next
return slow
return None
⚙️ 时间与空间复杂度
-
时间复杂度：O(n)
-
空间复杂度：O(1)
3️⃣ 合并两个有序链表
🧠 题目描述
将两个升序链表合并为一个新的 升序链表 并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。
💡 思路解析：双指针归并法
-
使用一个虚拟头节点
dum； -
维护指针
cur，依次比较list1和list2的节点； -
将较小的节点接在
cur.next； -
最后连接剩余部分。
🧾 代码实现
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
cur = dum = ListNode(0)
while list1 and list2:
if list1.val < list2.val:
cur.next, list1 = list1, list1.next
else:
cur.next, list2 = list2, list2.next
cur = cur.next
cur.next = list1 if list1 else list2
return dum.next
⚙️ 时间与空间复杂度
-
时间复杂度：O(n + m)
-
空间复杂度：O(1)