链表数据结构详解 (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 基本操作

遍历

def traverse(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

反转

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

alt

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 反转列表

alt

题目: 反转一个单链表.

迭代法已在 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 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.3 环形链表检测

判断链表中是否有环 (Floyd 判圈算法). Floyd 判圈算法又称“龟兔赛跑”. 我们派两个指针, 一个每次走一步 (乌龟), 一个每次走两步 (兔子). 如果赛道有环, 兔子最终会追上乌龟; 如果没有环, 兔子会率先到达终点. alt

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.

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 链表相交

找到两个单链表相交的起始节点.

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): 简化边界条件, 尤其在头节点可能变化时.
双指针: 快慢指针找中点、判环; 前后指针删倒数节点.
递归: 适合反转、合并等, 但需注意递归深度.
就地操作: 反转、重排等尽量 O(1) 额外空间.

7.复杂度分析

操作	数组	链表
随机访问	O(1)	O(n)
头部插入	O(n)	O(1)
尾部插入	O(1) 均摊	O(n) 无尾指针, O(1) 有尾指针
删除节点	O(n)	O(1) 若已知前驱
查找	O(n)	O(n)

链表在频繁插入删除且不需要随机访问的场景下表现优异.