链表

基础结构

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

# 创建链表：1 -> 2 -> 3 -> 4 -> 5
def create_linked_list(values):
    dummy = ListNode(0)
    cur = dummy
    for v in values:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next

# 打印链表
def print_list(head):
    vals = []
    while head:
        vals.append(str(head.val))
        head = head.next
    print(" -> ".join(vals) if vals else "Empty")

# 测试
head = create_linked_list([1, 2, 3, 4, 5])
print_list(head)  # 1 -> 2 -> 3 -> 4 -> 5

反转链表

1. 反转整个链表

def reverse_list(head):
    """
    反转链表：迭代方法
    时间：O(n)，空间：O(1)
    """
    prev = None
    curr = head
    
    while curr:
        next_temp = curr.next  # 保存下一个节点
        curr.next = prev       # 反转指针
        prev = curr            # prev 前移
        curr = next_temp       # curr 前移
    
    return prev

# 测试
head = create_linked_list([1, 2, 3, 4, 5])
print_list(reverse_list(head))  # 5 -> 4 -> 3 -> 2 -> 1

2. 反转链表（递归）

def reverse_list_recursive(head):
    """
    反转链表：递归方法
    """
    if not head or not head.next:
        return head
    
    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    
    return new_head

3. 反转前 N 个节点

def reverse_n(head, n):
    """
    反转链表的前 n 个节点
    """
    successor = None  # 第 n+1 个节点
    
    def reverse(head, n):
        nonlocal successor
        if n == 1:
            successor = head.next
            return head
        
        new_head = reverse(head.next, n - 1)
        head.next.next = head
        head.next = successor
        
        return new_head
    
    return reverse(head, n)

# 测试
head = create_linked_list([1, 2, 3, 4, 5])
print_list(reverse_n(head, 3))  # 3 -> 2 -> 1 -> 4 -> 5

4. 反转链表 II

def reverse_between(head, left, right):
    """
    反转从位置 left 到 right 的链表节点
    例如：1 -> 2 -> 3 -> 4 -> 5，left=2, right=4
    结果：1 -> 4 -> 3 -> 2 -> 5
    """
    dummy = ListNode(0)
    dummy.next = head
    
    # 找到 left 前一个节点
    prev = dummy
    for _ in range(left - 1):
        prev = prev.next
    
    # 开始反转
    start = prev.next
    curr = start
    prev_node = None
    
    for _ in range(right - left + 1):
        next_temp = curr.next
        curr.next = prev_node
        prev_node = curr
        curr = next_temp
    
    # 连接
    prev.next = prev_node
    start.next = curr
    
    return dummy.next

环形链表检测

1. 快慢指针检测环形

def has_cycle(head):
    """
    检测链表是否有环
    时间：O(n)，空间：O(1)
    """
    if not head or not head.next:
        return False
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False

2. 找到环形链表的入口

def detect_cycle(head):
    """
    找到环形链表的入口节点
    如果无环返回 None
    """
    if not head or not head.next:
        return None
    
    # 第一步：快慢指针相遇
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    
    if not fast or not fast.next:
        return None  # 无环
    
    # 第二步：找入口
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow

# 测试
# 创建带环链表：1 -> 2 -> 3 -> 4 -> 5 -> 3
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(4):
    nodes[i].next = nodes[i + 1]
nodes[4].next = nodes[2]  # 尾巴连接第三个节点

entry = detect_cycle(nodes[0])
print(entry.val if entry else None)  # 3

3. 环形链表 II（数学证明）

为什么这个算法有效？

设：
- 从头到入口的距离：a
- 环的长度：b
- 相遇时快指针走了：F（slow 走了 F/2）

快慢指针相遇时：
F = a + m*b  (fast 绕了 m 圈)
F/2 = a + n*b  (slow 绕了 n 圈)

所以：a + n*b = (a + m*b)/2
     2a + 2n*b = a + m*b
     a = (m - 2n)*b

说明从相遇点继续走 a 步，会回到入口点

合并有序链表

def merge_two_lists(l1, l2):
    """
    合并两个有序链表
    """
    dummy = ListNode(0)
    cur = dummy
    
    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    
    cur.next = l1 or l2
    
    return dummy.next

# 测试
l1 = create_linked_list([1, 3, 5])
l2 = create_linked_list([2, 4, 6])
print_list(merge_two_lists(l1, l2))  # 1 -> 2 -> 3 -> 4 -> 5 -> 6

删除倒数第 N 个节点

def remove_nth_from_end(head, n):
    """
    删除链表的倒数第 n 个节点
    使用哑节点简化边界处理
    """
    dummy = ListNode(0)
    dummy.next = head
    
    # 第一个指针先走 n+1 步
    first = dummy
    for _ in range(n + 1):
        first = first.next
    
    # 一起走，直到第一个到末尾
    second = dummy
    while first:
        first = first.next
        second = second.next
    
    # 删除节点
    second.next = second.next.next
    
    return dummy.next

# 测试
head = create_linked_list([1, 2, 3, 4, 5])
print_list(remove_nth_from_end(head, 2))  # 1 -> 2 -> 3 -> 5

相交链表

def get_intersection_node(headA, headB):
    """
    找到两个链表相交的起始节点
    """
    if not headA or not headB:
        return None
    
    # 拼接 A+B 和 B+A
    pA, pB = headA, headB
    
    while pA != pB:
        pA = headB if not pA else pA.next
        pB = headA if not pB else pB.next
    
    return pA

# 测试
# 创建相交链表：A: 1 -> 2 -> 3
#               B:    6 -> 3
# 相交于节点 3

链表排序

def sort_list(head):
    """
    对链表进行 O(n log n) 排序（归并排序）
    """
    if not head or not head.next:
        return head
    
    # 找中点
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    mid = slow.next
    slow.next = None
    
    # 递归排序
    left = sort_list(head)
    right = sort_list(mid)
    
    # 合并
    return merge_two_lists(left, right)

常见题型总结

题型	方法	关键点
反转链表	双指针/递归	保存下一个节点
环形检测	快慢指针	O(1) 空间
环形入口	快慢指针+数学	两阶段相遇
删除节点	哑节点	简化边界
合并链表	双指针	依次比较
相交节点	拼接 A+B	数学 trick

[[返回算法首页|algorithm/index]]