链表的基础算法(Python）

1. 什么是链表

想象一下，你有一串珍珠项链。每颗珍珠（数据）都通过一根细线（指针）连接到下一颗珍珠。你可以轻松地在中间插入一颗新珍珠，或者取下一颗旧的，只需要调整几根线的连接，而不必像数组那样，把后面所有的珍珠都挪动位置。这就是链表（Linked List）——一种线性数据结构，它的元素在内存中不必连续存放，每个元素由一个节点（Node）表示，节点包含数据域和指向下一个节点的指针（引用）。

相比数组，链表的插入与删除效率更高，但代价是随机访问较慢，因为你必须从第一颗珍珠开始，一颗一颗数过去。

常见的链表类型主要有三种：

• 单链表（Singly Linked List）：只能单向前进。
• 双向链表（Doubly Linked List）：可以向前也可以向后。
• 循环链表（Circular Linked List）：首尾相连，形成一个环。

2. 单链表

2.1 节点定义

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

这个结构非常直观：val 就是珍珠本身（存储的数据），next 就是那根指向下一颗珍珠的线。如果 next 是 None，那就意味着这是项链的最后一颗珍珠。

2.2 基本操作

掌握了节点的结构，接下来看看如何操作这根“珍珠项链”。

遍历链表：从头开始，沿着 next 指针一路走下去。

def tra verse(head):
    cur = head
    while cur:
        print(cur.val, end=' -> ')
        cur = cur.next
    print('None')

在头部插入节点：这就像制作一条新项链，先把新珍珠的线连到旧的第一颗珍珠上，然后宣布这颗新珍珠成为项链的新起点。

def insert_at_head(head, val):
    new_node = ListNode(val)
    new_node.next = head
    return new_node

在尾部插入节点：需要先走到项链的末端，再把最后一颗珍珠的线系到新珍珠上。

def insert_at_tail(head, val):
    new_node = ListNode(val)
    if not head:
        return new_node
    cur = head
    while cur.next:
        cur = cur.next
    cur.next = new_node
    return head

删除节点：找到目标珍珠的前一颗珍珠，然后把它的线直接绕过目标，连接到再下一颗珍珠上。目标珍珠虽然还在，但已经没有任何线连接它，相当于从项链上取下来了。

def delete_node(head, target):
    if not head:
        return None
    if head.val == target:
        return head.next
    cur = head
    while cur.next:
        if cur.next.val == target:
            cur.next = cur.next.next
            return head
        cur = cur.next
    return head

反转链表：这是一个经典操作。思路是，把每一颗珍珠的指向都反过来。你需要三个指针：一个指向前一颗珍珠（prev），一个指向当前珍珠（cur），还有一个临时保存下一颗珍珠（next_node），防止断线。

def reverse_list(head):
    prev = None
    cur = head
    while cur:
        next_node = cur.next
        cur.next = prev
        prev = cur
        cur = next_node
    return prev

3. 双向链表

单链表只能向前走，万一错过了想回头怎么办？双向链表给每张“纸条”加上了“上一张纸条的位置”。这样你就可以自由前进或后退了。

每个节点有两个指针：prev 和 next。

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

在头部插入节点：操作稍多一步，需要维护好新节点和原头节点之间的双向链接。

def dll_insert_head(head, val):
    new_node = DoubleListNode(val)
    new_node.next = head
    if head:
        head.prev = new_node
    return new_node

删除节点：在已知节点引用的情况下，删除变得异常简单，只需要调整其前驱和后继节点的指针即可。

def dll_delete_node(node):
    if node.prev:
        node.prev.next = node.next
    if node.next:
        node.next.prev = node.prev

4. 循环链表

单循环链表：让尾节点的 next 指向头节点，形成一个环。约瑟夫问题就是它的经典应用场景。

def create_circular_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    cur.next = head
    return head

遍历循环链表时需要特别注意终止条件，常用的方法是从头开始，当再次遇到头节点时停止。

5. 典型例题

5.1 反转列表

迭代法已经在 2.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

递归过程就像是把一列火车从后向前一节节卸下来重新组装。尽管代码简洁，但要小心递归深度过大可能导致栈溢出。

5.2 合并两个有序链表

这就像有两队按身高排好队的小朋友，我们要把他们合并成一支新队伍。策略很简单：每次比较两队队首的身高，选较矮的加入新队伍，然后该队指针后移。

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 if l1 else l2
    return dummy.next

5.3 环形链表检测

判断链表中是否有环，经典的解决方案是 Floyd 判圈算法，又称“龟兔赛跑”算法。

我们派两个指针，一个每次走一步（乌龟），一个每次走两步（兔子）。如果赛道有环，兔子最终会追上乌龟；如果没有环，兔子会率先到达终点（None）。

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

如果要求返回环的入口节点，算法需要稍作调整：

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

为什么这样能找到入口？简单来说，设头节点到环入口距离为 a，入口到相遇点距离为 b，环长为 L。第一次相遇时，快指针路程是慢指针的两倍，可以推导出 a 一定是 L 的整数倍减去 b。所以让一个指针从开头走 a 步，另一个从相遇点走 a 步（在环里相当于走了 L - b + b 等），它们必定在入口重合。

5.4 删除链表的倒数第 N 个节点

利用双指针技巧，让两个指针相距 N 步。当前面的指针走到链表末尾时，后面的指针正好指向待删除节点的前驱。

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    first = second = dummy
    for _ in range(n + 1):
        first = first.next
    while first:
        first = first.next
        second = second.next
    second.next = second.next.next
    return dummy.next

5.5 回文链表

判断链表是否为回文。一个巧妙的思路是：先找到链表中点，反转后半部分，然后同时从头部和反转后的后半部头部开始比较。

def is_palindrome(head):
    if not head or not head.next:
        return True
    # 找中点
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # 反转后半
    prev = None
    while slow:
        next_node = slow.next
        slow.next = prev
        prev = slow
        slow = next_node
    # 比较
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

5.6 两两交换链表中的节点

给定 1->2->3->4，返回 2->1->4->3。关键在于维护好一个“前驱”指针（prev），每次交换一对节点后，更新这个前驱指针。

def swap_pairs(head):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next and prev.next.next:
        first = prev.next
        second = first.next
        first.next = second.next
        second.next = first
        prev.next = second
        prev = first
    return dummy.next

5.7 链表相交

找到两个单链表相交的起始节点。一个巧妙的解法是：让两个指针分别从两个链表头出发，当走到末尾时，切换到另一个链表的头部继续走。如果两链表相交，它们最终会在交点相遇；如果不相交，最终会同时到达 None。

def get_intersection_node(headA, headB):
    pa, pb = headA, headB
    while pa != pb:
        pa = pa.next if pa else headB
        pb = pb.next if pb else headA
    return pa

6. 链表常用技巧总结

• 哑节点（Dummy Node）：在链表头部前面添加一个不存储实际值的节点，可以极大地简化边界条件处理，尤其是在头节点可能发生变化的时候。
• 双指针：快慢指针用于找中点、判断环；前后指针用于删除倒数第 N 个节点。
• 递归：非常适合处理反转、合并等具有自相似性的问题，但需要注意递归深度可能导致的栈溢出。
• 就地操作：对于反转、重排等操作，尽量使用 O(1) 的额外空间，直接在原链表上修改指针。

7. 复杂度分析

从表格可以清晰地看出，链表在需要频繁插入、删除且不需要随机访问的场景下表现优异，而数组则在需要快速按索引访问时更胜一筹。选择哪种数据结构，取决于你的具体需求。