Python链表基础案例有哪些？

wen python案例 2026-06-08 04:33:10 1

Python链表基础案例有哪些？一文掌握链表核心操作与实战代码

目录导读

链表到底是什么？为什么Python中要学它？
单链表：最简单的链表结构及基础案例
双链表：前后都能走的进阶案例
循环链表：首尾相接的特殊案例
链表常见操作案例：增删改查与反转
链表与列表的性能对比：什么时候用链表？
常见面试题案例：检测环、找中点、合并两个有序链表
总结与Q&A

链表到底是什么？为什么Python中要学它？

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指针域，与Python的内置列表（基于动态数组）不同，链表在内存中不必连续存储，因此插入和删除操作更为灵活。

为什么Python开发者要学链表？

Python的list虽然方便，但insert(0, x)或pop(0)的时间复杂度为O(n)。
链表的插入/删除（已知位置）时间复杂度为O(1)，适合高频修改的场景。
许多经典算法（如LRU缓存、图邻接表）底层依赖链表结构。

常见误区：链表的“随机访问”速度慢（O(n)），而列表的随机访问是O(1)，所以链表并非万能，要根据场景选择。

问：Python列表的底层是数组，链表比它好在哪？
答：列表在头部插入/删除时需要移动所有元素，时间复杂度O(n)；链表只需修改指针，时间复杂度O(1)，但列表支持通过索引直接访问，链表必须从头遍历。

单链表：最简单的链表结构及基础案例

节点定义

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

基础案例：创建并遍历单链表

# 创建节点
node1 = ListNode(10)
node2 = ListNode(20)
node3 = ListNode(30)
# 串联节点
node1.next = node2
node2.next = node3
# 遍历打印
current = node1
while current:
    print(current.val, end=" -> ")
    current = current.next
# 输出: 10 -> 20 -> 30 -> None

添加头节点与尾节点

def add_at_head(head, val):
    new_node = ListNode(val)
    new_node.next = head
    return new_node   # 新节点成为头
def add_at_tail(head, val):
    if not head:
        return ListNode(val)
    cur = head
    while cur.next:
        cur = cur.next
    cur.next = ListNode(val)
    return head

案例应用场景：通讯录链表、文本编辑器的撤销操作栈。

问：为什么插入头节点时要返回新节点？
答：因为头指针改变了，必须通过返回值更新外部引用，否则原head仍指向旧头节点。

双链表：前后都能走的进阶案例

双链表的每个节点多了一个prev指针，指向前一个节点。

节点定义

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

基础案例：双向遍历

# 创建三个节点并连接
a = DListNode(1)
b = DListNode(2)
c = DListNode(3)
a.next = b
b.prev = a
b.next = c
c.prev = b

双向删除节点（已知节点指针）

def delete_node(node):
    # 假设node不是None且存在前后节点
    prev_node = node.prev
    next_node = node.next
    if prev_node:
        prev_node.next = next_node
    if next_node:
        next_node.prev = prev_node
    # Python的GC会自动回收node

优势：删除给定节点时，不需要像单链表那样从头查找前驱节点。

问：双链表的prev指针会占用额外内存，值得吗？
答：对于需要频繁删除/反转操作（如浏览器前进后退、LRU缓存），双链表节省了查找前驱的时间，空间换时间。

循环链表：首尾相接的特殊案例

循环链表是一种特殊的单链表,其尾节点的next指向头节点（或head），形成一个环。

基础案例：创建并遍历（注意终止条件）

def create_circular_list(vals):
    if not vals:
        return None
    head = ListNode(vals[0])
    cur = head
    for v in vals[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    cur.next = head   # 尾指针指向头
    return head
# 遍历（只遍历10个节点避免死循环）
head = create_circular_list([1,2,3,4])
cur = head
count = 0
while cur and count < 10:
    print(cur.val, end=" -> ")
    cur = cur.next
    count += 1
# 输出: 1 -> 2 -> 3 -> 4 -> 1 -> 2 -> ...

经典应用：约瑟夫环问题（Josephus Problem）

def josephus_survivor(n, k):
    # 创建循环链表
    head = ListNode(1)
    prev = head
    for i in range(2, n+1):
        prev.next = ListNode(i)
        prev = prev.next
    prev.next = head   # 闭合
    # 模拟淘汰
    cur = head
    while cur.next != cur:   # 只剩一个节点
        for _ in range(k-2):  # 走k-1步（从1开始计数）
            cur = cur.next
        # 删除下一个节点
        cur.next = cur.next.next
        cur = cur.next
    return cur.val
print(josephus_survivor(7, 3))  # 输出4

问：循环链表和普通链表如何区分？
答：普通链表尾节点next为None，循环链表尾节点next指向头节点，检测方法可用快慢指针（Floyd判环算法）。

链表常见操作案例：增删改查与反转

1 查找中间节点（快慢指针法）

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

2 反转单链表（迭代法）

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 合并两个有序链表（递归/迭代）

def merge_sorted(l1, l2):
    # 递归版本（简洁但栈深度有风险）
    if not l1 or not l2:
        return l1 or l2
    if l1.val < l2.val:
        l1.next = merge_sorted(l1.next, l2)
        return l1
    else:
        l2.next = merge_sorted(l1, l2.next)
        return l2

问：反转链表时为什么需要临时变量next_node？
答：因为一旦将cur.next指向prev，原链表就断了，不保存就找不到后续节点。

链表与列表的性能对比：什么时候用链表？

操作	Python `list`	链表 (单链表)
随机访问	O(1)	O(n)
头部插入	O(n)	O(1)
尾部插入	O(1)*	O(n)（若无尾指针）
中间插入（已知位置）	O(n)	O(1)（已知前驱）
内存占用	连续内存，预分配	每个节点额外存储指针
缓存友好度	高	低（内存不连续）

选择建议：

频繁随机访问：用列表。
频繁头部插入/删除：用链表（或collections.deque）。
内存紧张：看情况，链表指针开销可能超过列表预分配。

问：Python的deque与链表关系？
答：collections.deque基于双端队列（双向链表+数组块），是链表的高效Python实现，适合栈和队列。

常见面试题案例：检测环、找中点、合并两个有序链表

案例1：检测链表是否有环（Floyd判环算法）

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

案例2：找到环的入口节点

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

案例3：删除链表的倒数第N个节点（双指针技巧）

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    slow = fast = dummy
    # fast先走n+1步
    for _ in range(n+1):
        fast = fast.next
    # 同步移动直到fast为None
    while fast:
        slow = slow.next
        fast = fast.next
    # 删除slow的下一个节点
    slow.next = slow.next.next
    return dummy.next