算法通关训练营 · 线性结构篇（链表：指针的艺术）（已并入旗舰课 469）

3 浏览3 访客

本课已并入《算法通关旗舰课：从链表到排序的 30 讲完整路径》（30 讲完整路径一条走完）。原付费学员仍可继续访问，建议前往算法通关旗舰课体验完整体系。

课程简介

这是必学必会「算法」科目的线性结构专题课，对应缺口体系 C 系列（线性表与链式结构）。从链表的节点与指针讲起，带你手写单链表、双向链表、循环链表的增删查改，再攻克反转、快慢指针、哨兵节点等经典技巧，最后用 LRU 缓存与约瑟夫环把知识落到真实系统。每一节都配知识单元 + 实战题。

学习目标

能说清数组与链表的核心差异及各自的适用场景
能手写单 / 双 / 循环链表的插入、删除、遍历，并规避"断链"错误
掌握反转、快慢指针、哨兵节点等链表经典技巧
理解链表在 LRU 缓存、浏览器历史、操作系统调度中的真实应用

章节概览

第1节链表基础：节点、指针与遍历（本节，缺口 C3）
第2节单链表增删与哨兵节点（缺口 C3 延伸）
第3节双向链表与循环链表（缺口 C3）
第4节经典技巧：反转与快慢指针（缺口 C7）
第5节实战：LRU 缓存与约瑟夫环（工程综合）

---

图：算法通关训练营·线性结构篇的知识延伸地图

参考代码（Python）

链表最该亲手写熟的就是节点定义与指针改向，下面给出单链表的核心骨架：

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

def traverse(head):
    cur = head
    while cur is not None:
        print(cur.val); cur = cur.next

def insert_after(p, val):
    new = Node(val)
    new.next = p.next   # 先接后面，避免断链
    p.next = new

def delete_after(p):
    if p.next is not None:
        p.next = p.next.next

注意 insert_after 的顺序：务必先 new.next = p.next 再 p.next = new，否则后半条链会丢失。