链表详解：指针的穿针引线

画图是调试链表的最好方法，每一步指针变化都画出来！

链表是我刷题过程中觉得最"绕"的数据结构之一。不像数组那样可以直接用下标访问，链表的操作全靠指针穿针引线。刚开始经常写出死循环或者丢失节点，后来发现画图是最好的办法——把每一步指针的指向都画出来，问题就清晰了。

链表题目的核心技巧就那么几个：虚拟头节点、快慢指针、反转链表，掌握这些，大部分题目都能解决。

什么是链表

链表是一种线性数据结构，每个元素（节点）包含数据和指向下一个节点的指针。

1
2
3
4
5
6
7
单链表：
  head → [1] → [2] → [3] → [4] → null
          ↑     ↑     ↑     ↑
         节点  节点  节点  节点

双向链表：
  null ← [1] ⇄ [2] ⇄ [3] ⇄ [4] → null

节点定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 单链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 双向链表节点
struct DoublyListNode {
    int val;
    DoublyListNode* prev;
    DoublyListNode* next;
    DoublyListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};

链表 vs 数组

操作 数组 链表
随机访问 O(1) O(n)
头部插入 O(n) O(1)
尾部插入 O(1) O(n)*
中间插入 O(n) O(1)**
内存布局 连续 分散

*尾部插入如果有尾指针则是O(1)
**找到位置后插入是O(1)，找位置需要O(n)

基本操作

遍历链表

1
2
3
4
5
6
7
void traverse(ListNode* head) {
    ListNode* curr = head;
    while (curr) {
        cout << curr->val << " ";
        curr = curr->next;
    }
}

在头部插入

1
2
3
4
5
ListNode* insertAtHead(ListNode* head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    return newNode;  // 新的头节点
}

在尾部插入

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* insertAtTail(ListNode* head, int val) {
    ListNode* newNode = new ListNode(val);
    
    if (!head) return newNode;
    
    ListNode* curr = head;
    while (curr->next) {
        curr = curr->next;
    }
    curr->next = newNode;
    
    return head;
}

删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* deleteNode(ListNode* head, int val) {
    // 虚拟头节点，简化边界处理
    ListNode dummy(0);
    dummy.next = head;
    
    ListNode* prev = &dummy;
    ListNode* curr = head;
    
    while (curr) {
        if (curr->val == val) {
            prev->next = curr->next;
            delete curr;
            break;
        }
        prev = curr;
        curr = curr->next;
    }
    
    return dummy.next;
}

核心技巧：虚拟头节点

链表操作中，头节点经常需要特殊处理。使用**虚拟头节点（dummy node）**可以简化代码，统一操作逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 没有虚拟头节点：需要单独处理头节点
ListNode* removeElements(ListNode* head, int val) {
    // 删除头部所有等于val的节点
    while (head && head->val == val) {
        head = head->next;
    }
    
    if (!head) return nullptr;
    
    ListNode* curr = head;
    while (curr->next) {
        if (curr->next->val == val) {
            curr->next = curr->next->next;
        } else {
            curr = curr->next;
        }
    }
    
    return head;
}

// 使用虚拟头节点：代码更简洁
ListNode* removeElements(ListNode* head, int val) {
    ListNode dummy(0);
    dummy.next = head;
    
    ListNode* curr = &dummy;
    while (curr->next) {
        if (curr->next->val == val) {
            curr->next = curr->next->next;
        } else {
            curr = curr->next;
        }
    }
    
    return dummy.next;
}

核心技巧：快慢指针

快慢指针是链表中最常用的技巧之一。

找中间节点

1
2
3
4
5
6
7
8
9
10
11
ListNode* findMiddle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;
}

执行过程：

1
2
3
4
5
6
7
8
链表: 1 → 2 → 3 → 4 → 5

初始:  slow=1, fast=1
第1步: slow=2, fast=3
第2步: slow=3, fast=5
第3步: fast->next=null，停止

中间节点: 3

判断是否有环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            return true;  // 相遇说明有环
        }
    }
    
    return false;
}

找环的入口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    
    // 第一步：找到相遇点
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            // 第二步：从head和相遇点同时出发
            ListNode* p1 = head;
            ListNode* p2 = slow;
            
            while (p1 != p2) {
                p1 = p1->next;
                p2 = p2->next;
            }
            
            return p1;  // 环的入口
        }
    }
    
    return nullptr;
}

为什么这样能找到环入口？这涉及到一点数学推导，简单来说：设头到环入口距离为a，环入口到相遇点距离为b，环的长度为c。相遇时slow走了a+b，fast走了a+b+nc（n圈）。因为fast是slow的两倍速度，所以2(a+b) = a+b+nc，得到a = nc-b。这意味着从头走a步和从相遇点走a步会在入口相遇。

核心技巧：反转链表

反转链表是链表操作的基础，很多题目都会用到。

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    
    while (curr) {
        ListNode* next = curr->next;  // 保存下一个节点
        curr->next = prev;             // 反转指针
        prev = curr;                   // prev前进
        curr = next;                   // curr前进
    }
    
    return prev;
}

执行过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
原链表: 1 → 2 → 3 → null

初始: prev=null, curr=1

Step 1: next=2, 1→null, prev=1, curr=2
        null ← 1   2 → 3 → null

Step 2: next=3, 2→1, prev=2, curr=3
        null ← 1 ← 2   3 → null

Step 3: next=null, 3→2, prev=3, curr=null
        null ← 1 ← 2 ← 3

结果: 3 → 2 → 1 → null

递归法

1
2
3
4
5
6
7
8
9
10
11
ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;  // 让下一个节点指向自己
    head->next = nullptr;      // 断开原来的指向
    
    return newHead;
}

经典问题：合并两个有序链表

LeetCode 21: 将两个升序链表合并为一个新的升序链表。

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* curr = &dummy;
    
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }
    
    // 接上剩余部分
    curr->next = l1 ? l1 : l2;
    
    return dummy.next;
}

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
l1: 1 → 2 → 4
l2: 1 → 3 → 4

Step 1: 1 <= 1, 取l1的1
        dummy → 1

Step 2: 2 > 1, 取l2的1
        dummy → 1 → 1

Step 3: 2 <= 3, 取l1的2
        dummy → 1 → 1 → 2

Step 4: 4 > 3, 取l2的3
        dummy → 1 → 1 → 2 → 3

Step 5: 4 <= 4, 取l1的4
        dummy → 1 → 1 → 2 → 3 → 4

Step 6: l1为空，接上l2剩余的4
        dummy → 1 → 1 → 2 → 3 → 4 → 4

结果: 1 → 1 → 2 → 3 → 4 → 4

时间复杂度: O(m + n)
空间复杂度: O(1)

经典问题：删除倒数第N个节点

LeetCode 19: 删除链表的倒数第N个节点。

思路

用快慢指针：让fast先走N步，然后fast和slow一起走，当fast到达末尾时，slow刚好在倒数第N个节点的前一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0);
    dummy.next = head;
    
    ListNode* fast = &dummy;
    ListNode* slow = &dummy;
    
    // fast先走n+1步
    for (int i = 0; i <= n; ++i) {
        fast = fast->next;
    }
    
    // 一起走，直到fast到达末尾
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    
    // 删除slow的下一个节点
    slow->next = slow->next->next;
    
    return dummy.next;
}

执行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
链表: 1 → 2 → 3 → 4 → 5, n=2

dummy → 1 → 2 → 3 → 4 → 5 → null

Step 1: fast先走3步 (n+1=3)
        fast指向3

Step 2: 一起走
        fast=4, slow=1
        fast=5, slow=2
        fast=null, slow=3

Step 3: 删除slow的下一个节点(4)
        3 → 5

结果: 1 → 2 → 3 → 5

经典问题：相交链表

LeetCode 160: 找到两个单链表相交的起始节点。

思路

让两个指针分别从两个链表头出发，走到末尾后跳到另一个链表头继续走。如果有交点，它们会在交点相遇；如果没有交点，它们会同时到达null。

原理：设链表A长度为a，链表B长度为b，公共部分长度为c。指针1走的路径：a + (b-c)，指针2走的路径：b + (a-c)。两者长度相等，所以会同时到达交点。

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    if (!headA || !headB) return nullptr;
    
    ListNode* pA = headA;
    ListNode* pB = headB;
    
    while (pA != pB) {
        pA = pA ? pA->next : headB;
        pB = pB ? pB->next : headA;
    }
    
    return pA;
}

执行过程

1
2
3
4
5
6
7
8
A: 1 → 2 ↘
           6 → 7
B: 3 → 4 → 5 ↗

pA的路径: 1 → 2 → 6 → 7 → null → 3 → 4 → 5 → 6
pB的路径: 3 → 4 → 5 → 6 → 7 → null → 1 → 2 → 6

相遇点: 6

经典问题：回文链表

LeetCode 234: 判断链表是否是回文链表。

思路

  1. 用快慢指针找到中点
  2. 反转后半部分
  3. 比较前半部分和后半部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
    
    // 1. 找中点
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // 2. 反转后半部分
    ListNode* secondHalf = reverseList(slow->next);
    
    // 3. 比较
    ListNode* p1 = head;
    ListNode* p2 = secondHalf;
    bool result = true;
    
    while (p2) {
        if (p1->val != p2->val) {
            result = false;
            break;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    
    // 4. 恢复链表（可选）
    slow->next = reverseList(secondHalf);
    
    return result;
}

执行过程

1
2
3
4
5
6
7
8
9
10
11
链表: 1 → 2 → 2 → 1

找中点: slow=2 (第一个2)

反转后半部分: 2 → 1 变成 1 → 2

比较:
  p1=1, p2=1 ✓
  p1=2, p2=2 ✓

结果: true

经典问题：排序链表

LeetCode 148: 对链表进行排序，要求O(n log n)时间复杂度。

思路

归并排序最适合链表：找中点、分割、递归排序、合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;
    
    // 1. 找中点并分割
    ListNode* slow = head;
    ListNode* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    ListNode* mid = slow->next;
    slow->next = nullptr;  // 断开
    
    // 2. 递归排序
    ListNode* left = sortList(head);
    ListNode* right = sortList(mid);
    
    // 3. 合并
    return mergeTwoLists(left, right);
}

常见陷阱

1. 忘记保存next指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// ❌ 错误：修改指针前没有保存next
while (curr) {
    curr->next = prev;
    prev = curr;
    curr = curr->next;  // 已经被修改了！
}

// ✅ 正确：先保存next
while (curr) {
    ListNode* next = curr->next;  // 先保存
    curr->next = prev;
    prev = curr;
    curr = next;
}

2. 空指针访问

1
2
3
4
5
// ❌ 危险：没有检查curr是否为空
while (curr->next) { ... }

// ✅ 安全：先检查curr
while (curr && curr->next) { ... }

3. 忘记处理头节点

1
2
3
// 使用虚拟头节点可以避免很多边界问题
ListNode dummy(0);
dummy.next = head;

思维导图

graph TD
    A[链表] --> B[基本操作]
    A --> C[核心技巧]
    A --> D[经典问题]
    
    B --> B1[遍历]
    B --> B2[插入/删除]
    
    C --> C1[虚拟头节点]
    C --> C2[快慢指针]
    C --> C3[反转链表]
    
    D --> D1[合并链表]
    D --> D2[环检测]
    D --> D3[回文链表]
    D --> D4[排序链表]
    
    style A fill:#FFE4B5
    style C fill:#90EE90
    style D fill:#87CEEB

总结

核心要点

  1. 画图是最好的调试方法：每一步指针变化都画出来
  2. 虚拟头节点简化边界处理：特别是涉及删除头节点的情况
  3. 快慢指针解决大量问题：找中点、检测环、倒数第N个
  4. 反转链表是基础操作：很多题目都会用到

LeetCode推荐题单

入门：

  • 206 反转链表
  • 21 合并两个有序链表
  • 141 环形链表

进阶：

  • 19 删除倒数第N个节点
  • 160 相交链表
  • 234 回文链表

挑战：

  • 25 K个一组反转链表
  • 148 排序链表
  • 146 LRU缓存

推荐阅读：