前言

使用语言 Python, 只针对 LC Medium 和 Hard 题, 面向面试刷题
Note: 除非你面前端 (加上 JS) , 否则统一使用 Python 进行刷题

基本操作

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Dummy（哨兵节点）

  • 用于: Merge Lists, Remove Node, 任何可能改变头节点的情况
dummy = ListNode(0)
current = dummy

# ... 操作链表 ...

return dummy.next  # 返回真正的头节点

快慢指针找倒数

  • 找倒数第 N 个: fast 先走 N 步
# 找倒数第 N 个节点
dummy = ListNode(0, head)
slow = fast = dummy

# fast 先走 N 步
for _ in range(n):
    fast = fast.next

# 然后一起走，slow 会停在倒数第 N+1 个（方便删除）
while fast.next:  # 注意是 fast.next
    slow = slow.next
    fast = fast.next

# slow.next 就是倒数第 N 个
return slow.next

快慢指针找环

def detectCycle(head):
    # 第一步：快慢指针检测环
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # 无环
    
    # 第二步：找环入口
    # 关键：从 head 和相遇点同时出发，相遇点就是环入口
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow

快慢指针找中点

# 情况1：偶数个节点时，slow 停在中间偏左
# 1 -> 2 -> 3 -> 4，slow 停在 2
slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

# 情况2：偶数个节点时，slow 停在中间偏右
# 1 -> 2 -> 3 -> 4，slow 停在 3
slow, fast = head, head.next
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

反转链表

prev = None
current = head

while current:
    next_node = current.next  # 先存下一个
    current.next = prev       # 反转指向
    prev = current            # prev 前进
    current = next_node       # current 前进

return prev  # 新的头

删除节点

# 删除 current 的下一个节点
current.next = current.next.next

删除节点时的边界

# ❌ 错误：删除头节点时会出问题
def deleteNode(head, val):
    curr = head
    while curr.next:
        if curr.next.val == val:
            curr.next = curr.next.next
            return head
        curr = curr.next
    return head

# ✅ 正确：用 dummy 节点
def deleteNode(head, val):
    dummy = ListNode(0, head)
    curr = dummy
    while curr.next:
        if curr.next.val == val:
            curr.next = curr.next.next
            return dummy.next
        curr = curr.next
    return dummy.next

题目

LC 206

虽然是 Easy, 但属于必须得会的题

LC 21

虽然是 Easy, 但属于必须得会的题, 用哨兵节点

LC 19

正常来说找倒数节点 N 只要用 fast 先走 N 步, 让 fast 和 slow 之间永远相差 N 个节点, 但是考虑到删除的节点可能是 head, 所以这题需要 哨兵节点

LC 24

哨兵节点 + prev, 维护 prev.next (first) 和 prev.next.next (second), 重新维护链接, 最后 prev = first, 完成一轮 swap

LC 143

快慢指针找中点, 然后截断, 然后反转后半部分, 然后 merge

LC 141

虽然是 Easy, 但属于必须得会的题

LC 25

这题考到了递归, 先确定从当前 head 开始, 有 k 个 node 可以 reverse, 然后 reverse 从 head (curr) 开始的 k 个 node, 然后递归调用 head.next = self.reverseKGroup(curr, k), 最终返回 prev

LC 148

这题属于递归 + 快慢指针找中点 (断开) + merge 2 list, 之所以 mereg 可以 work, 是因为递归的本质就是最终的结果要嘛是单个 node, 要嘛是 None

sort(4,2,1,3)
 ├─ sort(4,2)
 │   ├─ sort(4)  → 已排序
 │   └─ sort(2)  → 已排序
 │   → merge(4,2) → 2,4（已排序）
 └─ sort(1,3)
     ├─ sort(1) → 已排序
     └─ sort(3) → 已排序
     → merge(1,3) → 1,3（已排序）

最终：
merge(2,4) 和 (1,3) → 1,2,3,4（已排序）