算法入门第二篇：链表的艺术：结构、操作与指针魔法

技术文档

引言：链表为何如此重要？

朋友，如果你已经仔细研读并练习了第一篇的内容，恭喜你！你已经掌握了算法分析的基础，以及数组这个最基本、也是最常用的数据结构。现在，我们将步入一个全新的世界——链表（Linked List）。

你可能会想，既然有了数组这么方便、可以直接通过索引访问的数据结构，为什么我们还需要链表呢？它们的区别在哪里？

核心原因在于它们的内存存储方式不同：

数组：元素在内存中是连续存储的。这意味着如果你有一个包含 10 个整数的数组，它们在内存中是挨个排列的。这带来了 O(1) 的随机访问速度（因为知道了起始地址和索引，就能直接跳到目标地址），但代价是，如果想在数组中间插入或删除元素，后面的所有元素都必须移动，这导致了 O(N) 的效率。
链表：元素在内存中是离散存储的。每个元素（我们称之为节点）除了存储数据本身，还会包含一个指针（或引用），指向下一个节点在内存中的地址。这就像寻宝游戏：你找到一个宝藏，里面有下一个宝藏的线索，然后你根据线索找到下一个宝藏，以此类推。

这种离散存储的特性，赋予了链表独特的优势：

动态大小： 链表的长度不是固定的，可以根据需要动态地增长或缩小，无需像数组那样预先分配连续的、可能很大的内存空间。
高效的插入和删除： 在链表的任意位置插入或删除一个节点，只需要修改少数几个指针的指向，时间复杂度是 O(1)（前提是已经定位到了要操作的节点位置）。相比数组的 O(N) 效率，这是巨大的提升。

当然，链表也有它的不足：

不支持随机访问： 想要访问链表中的第 K 个元素？抱歉，你必须从头开始，沿着指针一步步走到第 K 个节点，时间复杂度是 O(K)，在最坏情况下是 O(N)。
额外的空间开销： 每个节点除了存储数据，还需要存储一个或多个指针，这会带来额外的内存消耗。

在游戏开发中，链表可能不如数组那样频繁直接地用于存储大量连续数据（例如顶点、纹理坐标），但其动态性和高效插入删除的特性在某些场景下仍然非常有用，例如：

任务队列/消息队列： 在帧与帧之间处理一系列游戏事件或 AI 行为。
有限状态机（FSM）： 状态之间的转移可以看作链式结构。
LRU 缓存（Least Recently Used Cache）： 链表结合哈希表可以高效实现缓存淘汰机制。

理解链表，特别是它如何通过**指针（引用）**来连接离散的节点，是掌握复杂数据结构和算法的关键一步。面试中，链表题目是高频考点，因为它能很好地考察你对指针操作的理解和边界条件的把握。

链表基础：节点与结构

链表由一系列**节点（Node）**组成，每个节点至少包含两个部分：

数据域（Data）： 存储节点所包含的实际数据。
指针域（Next Pointer）： 存储指向下一个节点的引用或地址。

单链表（Singly Linked List）

单链表是最基本的链表形式，每个节点只有一个指针，指向它的下一个节点。

结构定义： 在 C# 中，我们通常会定义一个 ListNode 类来表示链表中的一个节点。

public class ListNode { public int val; // 节点存储的数据 public ListNode next; // 指向下一个节点的指针 // 构造函数 public ListNode(int val = 0, ListNode next = null) { this.val = val; this.next = next; }}

头结点（Head）： 链表的第一个节点。通过头结点，我们可以访问到整个链表。如果头结点为 null，表示链表为空。
尾结点（Tail）： 链表的最后一个节点。它的 next 指针通常指向 null。
虚拟头结点（Dummy Node / Sentinel Node）： 也称为哨兵节点。这是一个不存储实际数据的辅助节点，它的 next 指针指向链表的实际头结点。
- 优点： 在对链表头部进行插入或删除操作时，无需特殊处理头结点，代码会更简洁统一。例如，删除头结点时，可以直接操作 dummy.next，而不用担心头结点变为 null 的情况。在面试中，这是非常推荐使用的技巧。
C#
```
// 使用虚拟头结点ListNode dummyHead = new ListNode(0); // 虚拟头结点，值通常设为0或任意值dummyHead.next = actualHead; // 实际链表的头结点// 之后的所有操作都通过 dummyHead 开始，最后返回 dummyHead.next
```

双链表（Doubly Linked List）

双链表在单链表的基础上，每个节点多了一个指针，指向它的前一个节点。

结构定义：

public class DoublyListNode { public int val; public DoublyListNode next; // 指向下一个节点 public DoublyListNode prev; // 指向前一个节点 public DoublyListNode(int val = 0, DoublyListNode next = null, DoublyListNode prev = null) { this.val = val; this.next = next; this.prev = prev; }}

优点： 可以在 O(1) 时间内找到前一个节点，这在某些操作（如删除给定节点）时非常方便。
缺点： 额外的 prev 指针会增加空间开销，并且在插入/删除时需要维护更多的指针关系，操作稍微复杂一点。

本篇我们将主要聚焦于单链表，因为它是面试中的绝对主流，掌握了单链表，双链表的很多操作也能触类旁通。

基本操作

理解链表的基本操作是解题的前提。

创建链表：

// 创建一个链表: 1 -> 2 -> 3ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);

遍历链表： 从头结点开始，沿着 next 指针依次访问每个节点，直到遇到 null。

public void TraverseList(ListNode head) { ListNode current = head; // 从头结点开始 while (current != null) { // 当当前节点不为空时 Console.Write(current.val + \" -> \"); // 访问数据 current = current.next; // 移动到下一个节点 } Console.WriteLine(\"null\");}// 示例调用：TraverseList(head); // 输出：1 -> 2 -> 3 -> null

查找节点： 遍历链表，直到找到目标值或遍历到末尾。

public ListNode FindNode(ListNode head, int target) { ListNode current = head; while (current != null) { if (current.val == target) { return current; // 找到目标节点 } current = current.next; } return null; // 未找到}

插入节点：

头插法： 在链表头部插入新节点。

public ListNode InsertAtHead(ListNode head, int val) { ListNode newNode = new ListNode(val); newNode.next = head; // 新节点的next指向原头结点 return newNode; // 新节点成为新的头结点}

尾插法： 在链表尾部插入新节点。需要先找到尾结点。

public ListNode InsertAtTail(ListNode head, int val) { ListNode newNode = new ListNode(val); if (head == null) { // 如果链表为空，新节点就是头结点 return newNode; } ListNode current = head; while (current.next != null) { // 遍历到尾结点 current = current.next; } current.next = newNode; // 尾结点的next指向新节点 return head;}

中间插入： 在指定节点 prevNode 之后插入新节点。

public void InsertAfter(ListNode prevNode, int val) { if (prevNode == null) { Console.WriteLine(\"前置节点不能为 null。\"); return; } ListNode newNode = new ListNode(val); newNode.next = prevNode.next; // 新节点的next指向prevNode的下一个节点 prevNode.next = newNode; // prevNode的next指向新节点}

删除节点： 删除指定节点（通常是给定其前一个节点）或删除指定值的节点。

删除指定节点 nodeToDelete （如果已知其前一个节点 prevNode）：

public void DeleteNodeAfter(ListNode prevNode) { if (prevNode == null || prevNode.next == null) { Console.WriteLine(\"无法删除，前置节点或其后无节点。\"); return; } prevNode.next = prevNode.next.next; // prevNode的next跳过要删除的节点}

删除指定值 val 的节点（可能涉及头结点）：

public ListNode DeleteNodeByValue(ListNode head, int val) { // 使用虚拟头结点简化操作 ListNode dummy = new ListNode(0); dummy.next = head; ListNode current = dummy; while (current.next != null) { if (current.next.val == val) { current.next = current.next.next; // 跳过当前要删除的节点 // 注意：这里如果链表中有多个相同值的节点，会全部删除。 // 如果只删除第一个，这里需要加 break; } else { current = current.next; } } return dummy.next; // 返回实际的头结点}

经典面试题与解法：链表篇

理解了链表的基础，我们来挑战几个经典的链表面试题。它们将充分考验你对指针操作的熟练程度，以及对边界条件的思考。

1. 反转链表 (Reverse Linked List)

题目描述：

给你单链表的头节点 head，请你反转链表，并返回反转后的链表头节点。

示例：

输入: head = [1, 2, 3, 4, 5]

输出: [5, 4, 3, 2, 1]
解题思路 1：迭代法 (Iterative Method) - “三指针法”

这是最常用且推荐掌握的方法。我们需要三个指针来跟踪链表的状态：
1. prev：指向前一个节点，初始为 null（因为反转后，原头结点的 next 将变为 null）。
2. curr：指向当前正在处理的节点，初始为 head。
3. next_node (或 temp)：临时保存 curr 的下一个节点，防止 curr.next 被修改后丢失后续链表信息。
步骤：
1. 初始化 prev = null, curr = head。
2. 循环直到 curr 为 null（即遍历完整个链表）：
  
  a. 保存 curr 的下一个节点：next_node = curr.next。
  
  b. 将 curr 的 next 指针指向 prev（完成反转操作）。
  
  c. 移动 prev 指针：prev = curr。
  
  d. 移动 curr 指针：curr = next_node。
3. 循环结束后，prev 将指向原链表的尾部，也就是反转后链表的头部。
- 图解（以 1 -> 2 -> 3 -> null 为例）：
  - 初始: prev=null, curr=1, head=1
  - 第1次循环 (curr=1):
    - next_node = 2
    - 1.next = null (反转 1 的指向)
    - prev = 1
    - curr = 2
    - 链表状态: null <- 1 2 -> 3 -> null
  - 第2次循环 (curr=2):
    - next_node = 3
    - 2.next = 1 (反转 2 的指向)
    - prev = 2
    - curr = 3
    - 链表状态: null <- 1 <- 2 3 -> null
  - 第3次循环 (curr=3):
    - next_node = null
    - 3.next = 2 (反转 3 的指向)
    - prev = 3
    - curr = null
    - 链表状态: null <- 1 <- 2 <- 3
  - 循环结束。返回 prev，即 3。
- 代码实现：
  
  C#
```
public ListNode ReverseListIterative(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; // 1. 保存下一个节点 curr.next = prev;  // 2. 当前节点指向前一个节点 prev = curr;  // 3. prev 移动到当前节点 curr = nextTemp;  // 4. curr 移动到下一个节点 } return prev; // prev 最终是反转后链表的头}
```
- 复杂度分析：
  - 时间复杂度：O(N)。遍历了链表一次。
  - 空间复杂度：O(1)。只使用了常数个额外指针。
解题思路 2：递归法 (Recursive Method)

递归解法更加精妙，但理解起来可能稍微抽象。其核心思想是：
1. 基本情况： 如果链表为空或只有一个节点，那么它本身就是反转后的结果，直接返回 head。
2. 递归调用： 假设我们已经能够反转从 head.next 开始的子链表。
  - newHead = ReverseListRecursive(head.next)：这会返回反转后子链表的头。
3. 连接： 现在 head.next 节点（原链表中 head 的下一个节点）已经指向了 newHead 之前的那个节点（也就是 head）。我们需要让 head 的下一个节点指向 head 本身。
  - head.next.next = head
4. 断开： 然后，将 head 的 next 指针置为 null，因为它现在是反转后链表的尾部。
  - head.next = null
5. 返回： 返回 newHead，因为它是整个链表反转后的头。
- 图解（以 1 -> 2 -> 3 -> null 为例）：
  - ReverseListRecursive(1)
    - ReverseListRecursive(2)
      - ReverseListRecursive(3)
        
        ReverseListRecursive(null) -> 返回 null
        
        ReverseListRecursive(3) 收到 null，head=3。
        
        newHead (来自 ReverseListRecursive(2)) 此时是 null。
        
        3.next.next = 3 （这里 3.next 是 null，所以 null.next 会报错！这是递归解法的一个关键点，head.next 必须是有效的子链表头，即不能是末尾节点）
        
        实际上，当 head.next 是链表尾部（其 next 为 null）时，ReverseListRecursive(head.next) 会返回这个尾部节点本身。
        
        所以，更精确的理解是：当 head = 3 时，head.next = null。基本情况 head.next == null 满足，直接返回 3。
      - ReverseListRecursive(2) 收到 3，head=2。
        
        newHead = 3
        
        head.next.next = head 即 2.next.next = 2 (把 3 的 next 指向 2)
        
        head.next = null 即 2.next = null (把 2 的 next 断开)
        
        返回 newHead = 3
      - 此时链表状态：null <- 2 <- 3
    - ReverseListRecursive(1) 收到 3，head=1。
      - newHead = 3
      - head.next.next = head 即 1.next.next = 1 (把 2 的 next 指向 1)
      - head.next = null 即 1.next = null (把 1 的 next 断开)
      - 返回 newHead = 3
  - 最终结果：null <- 1 <- 2 <- 3，返回 3。
- 代码实现：
  
  C#
```
public ListNode ReverseListRecursive(ListNode head) { // 基本情况：链表为空或只有一个节点，直接返回 if (head == null || head.next == null) { return head; } // 递归反转子链表 // newHead 将是反转后子链表的头（即原链表的尾部） ListNode newHead = ReverseListRecursive(head.next); // 关键步骤： // 让当前节点的下一个节点的 next 指向当前节点 // 例如：原 1 -> 2 -> 3, 递归返回 newHead = 3 // head = 1, head.next = 2 // head.next.next = head; 相当于 2.next = 1 head.next.next = head; // 将当前节点的 next 指向 null (因为它现在是新链表的尾部) head.next = null; // 返回反转后的新链表头 return newHead;}
```
- 复杂度分析：
  - 时间复杂度：O(N)。每个节点都被访问一次。
  - 空间复杂度：O(N)。递归调用的深度最坏情况下等于链表长度（递归栈空间）。
思考： 迭代法更直观，更省空间，是面试中的首选。递归法更考验对递归理解的深度，能写出来也说明你思维很灵活。

2. 合并两个有序链表 (Merge Two Sorted Lists)

题目描述：

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：list1 = [1, 2, 4], list2 = [1, 3, 4]

输出：[1, 1, 2, 3, 4, 4]
解题思路 1：迭代法 (Iterative Method)

这是最常见的解法。我们需要一个**虚拟头结点（dummy node）**来简化代码，避免处理新链表头结点的特殊情况。

步骤：
1. 创建一个虚拟头结点 dummyHead，并用一个指针 tail 指向它（tail 将始终指向新链表的当前末尾）。
2. 使用两个指针 p1 和 p2 分别遍历 list1 和 list2。
3. 循环直到 p1 或 p2 有一个到达 null：
  
  a. 比较 p1.val 和 p2.val。
  
  b. 将值较小的节点接到 tail.next，然后将 tail 移动到这个新接上的节点。
  
  c. 被接上的那个链表的指针（p1 或 p2）向前移动一步。
4. 循环结束后，如果 p1 或 p2 还有剩余节点（因为其中一个链表可能更长），将剩余的链表直接接到 tail.next。
5. 返回 dummyHead.next，它就是合并后链表的实际头结点。
- 代码实现：
  
  C#
```
public ListNode MergeTwoListsIterative(ListNode list1, ListNode list2) { // 创建虚拟头结点，简化操作 ListNode dummyHead = new ListNode(0); ListNode tail = dummyHead; // tail 始终指向新链表的当前尾部 ListNode p1 = list1; ListNode p2 = list2; // 当两个链表都有元素时，进行比较合并 while (p1 != null && p2 != null) { if (p1.val <= p2.val) { tail.next = p1; // 将 p1 接到新链表尾部 p1 = p1.next; // p1 前进 } else { tail.next = p2; // 将 p2 接到新链表尾部 p2 = p2.next; // p2 前进 } tail = tail.next; // tail 移动到新接上的节点 } // 处理剩余部分：如果 list1 还有剩余，接上 list1 if (p1 != null) { tail.next = p1; } // 如果 list2 还有剩余，接上 list2 (只会有一个剩余) if (p2 != null) { tail.next = p2; } return dummyHead.next; // 返回实际的头结点}
```
- 复杂度分析：
  - 时间复杂度：O(M+N)，其中 M 和 N 分别是两个链表的长度。每个节点只被访问一次。
  - 空间复杂度：O(1)。只使用了常数个额外指针和一个虚拟头结点。
解题思路 2：递归法 (Recursive Method)

递归思路是：每次比较两个链表的头结点，把较小的那个作为当前合并链表的头结点，然后它的 next 指向其余部分的合并结果。

基本情况：
- 如果 list1 为空，返回 list2。
- 如果 list2 为空，返回 list1。
递归步骤：
1. 如果 list1.val <= list2.val：
  - list1.next = MergeTwoListsRecursive(list1.next, list2)
  - 返回 list1
2. 否则 (list1.val > list2.val)：
  - list2.next = MergeTwoListsRecursive(list1, list2.next)
  - 返回 list2
- 代码实现：
  
  C#
```
public ListNode MergeTwoListsRecursive(ListNode list1, ListNode list2) { // 基本情况 if (list1 == null) { return list2; } if (list2 == null) { return list1; } // 递归合并 if (list1.val <= list2.val) { // 将 list1 的下一个节点和 list2 进行合并，结果作为 list1.next list1.next = MergeTwoListsRecursive(list1.next, list2); return list1; // 返回 list1 作为当前合并部分的头 } else { // 将 list1 和 list2 的下一个节点进行合并，结果作为 list2.next list2.next = MergeTwoListsRecursive(list1, list2.next); return list2; // 返回 list2 作为当前合并部分的头 }}
```
- 复杂度分析：
  - 时间复杂度：O(M+N)。递归调用的次数是两个链表长度之和。
  - 空间复杂度：O(M+N)。递归栈的深度在最坏情况下是两个链表长度之和。
思考： 递归解法代码简洁优雅，但面试中通常更推荐迭代法，因为它不占用额外的递归栈空间，且更容易跟踪执行流程。但两种方法都应掌握。

3. 删除链表的倒数第 N 个结点 (Remove Nth Node From End of List)

题目描述：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例：

输入：head = [1, 2, 3, 4, 5], n = 2

输出：[1, 2, 3, 5]

解释：删除倒数第 2 个节点（即值为 4 的节点）。
解题思路：快慢指针 (Two Pointers - Fast and Slow)

这又是一个快慢指针的经典应用！为了找到倒数第 N 个节点，我们可以让一个指针（快指针）先走 N 步，然后另一个指针（慢指针）从头开始，和快指针一起同步前进。当快指针到达链表末尾时，慢指针正好指向倒数第 N 个节点。

但我们不是要删除倒数第 N 个节点本身，而是要删除它。删除链表节点通常需要知道它前一个节点。所以，我们可以让慢指针指向倒数第 N+1 个节点（即要删除节点的前一个节点）。

步骤：
1. 创建一个虚拟头结点 dummyHead，并将其 next 指向 head。这样做可以避免特殊处理删除原头结点的情况。
2. 初始化快指针 fast 和慢指针 slow 都指向 dummyHead。
3. 让 fast 指针先向前走 n + 1 步。这样 fast 和 slow 之间就相隔了 n 个节点。
  - 为什么要走 n+1 步？因为当 fast 到达链表末尾（null）时，slow 正好在要删除节点的前一个节点。
4. 然后，fast 和 slow 同时向前移动，直到 fast 到达链表的末尾（fast == null）。
5. 此时，slow 指针指向的节点就是倒数第 n 个节点的前一个节点。
6. 执行删除操作：slow.next = slow.next.next。
7. 返回 dummyHead.next。
- 图解（以 1 -> 2 -> 3 -> 4 -> 5, n = 2 为例）：
  - 初始: dummy -> 1 -> 2 -> 3 -> 4 -> 5
  - fast 走 n+1=3 步:
    - fast 第一次走: dummy -> 1
    - fast 第二次走: 1 -> 2
    - fast 第三次走: 2 -> 3
    - 现在 fast 指向 3。
    - slow 仍指向 dummy。
    - 链表状态: dummy -> 1 -> 2 -> [3] -> 4 -> 5 (slow 在 dummy，fast 在 3)
  - fast 和 slow 同时前进，直到 fast == null：
    - slow=1, fast=4
    - slow=2, fast=5
    - slow=3, fast=null (fast 走了 3 步，到头了)
    - 现在 slow 指向 3。
    - 要删除的是倒数第 2 个（即 4），slow 正好指向 4 的前一个节点。
  - slow.next = slow.next.next 即 3.next = 3.next.next (将 3 的 next 指向 5)。
  - 链表变为：dummy -> 1 -> 2 -> 3 -> 5
  - 返回 dummy.next，即 1。
- 代码实现：
  
  C#
```
public ListNode RemoveNthFromEnd(ListNode head, int n) { // 使用虚拟头结点，避免处理删除头结点的特殊情况 ListNode dummyHead = new ListNode(0); dummyHead.next = head; ListNode fast = dummyHead; ListNode slow = dummyHead; // fast 先走 n + 1 步 for (int i = 0; i <= n; i++) { // 注意是 <= n，所以走了 n+1 步 fast = fast.next; } // fast 和 slow 同时前进，直到 fast 走到链表末尾 while (fast != null) { fast = fast.next; slow = slow.next; } // 此时 slow 指向要删除节点的前一个节点 slow.next = slow.next.next; return dummyHead.next; // 返回实际的头结点}
```
- 复杂度分析：
  - 时间复杂度：O(N)。快指针遍历了一次链表。
  - 空间复杂度：O(1)。只使用了常数个额外指针和一个虚拟头结点。
思考： 快慢指针是解决链表问题的核心技巧之一，尤其适用于涉及相对位置（如倒数第 N 个、链表中间、环）的问题。

4. 环形链表 (Linked List Cycle)

题目描述：

给你一个链表的头节点 head，判断链表中是否存在环。

如果链表中存在环，则返回 true。否则，返回 false。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
解题思路：快慢指针 (Floyd’s Cycle-Finding Algorithm / Tortoise and Hare)

判断链表是否有环的经典算法是弗洛伊德判圈算法，也称龟兔赛跑算法。

核心思想是：使用两个指针，一个快指针（兔），一个慢指针（龟）。
- 慢指针： 每次移动一步。
- 快指针： 每次移动两步。
如果链表中存在环，那么快指针最终一定会追上慢指针（因为每次快指针都比慢指针多走一步，它们之间的距离会不断缩小）。如果链表中没有环，快指针会先到达链表末尾（null）。

步骤：
1. 初始化 slow = head，fast = head。
2. 循环直到 fast 或 fast.next 为 null（确保快指针能够移动两步）：
  
  a. slow 移动一步：slow = slow.next。
  
  b. fast 移动两步：fast = fast.next.next。
  
  c. 如果 slow == fast，说明快慢指针相遇，链表有环，返回 true。
3. 如果循环结束还没相遇，说明没有环，返回 false。
- 代码实现：
  
  C#
```
public bool HasCycle(ListNode head) { if (head == null || head.next == null) { return false; // 空链表或只有一个节点，不可能有环 } ListNode slow = head; ListNode fast = head; // 循环条件：fast 和 fast.next 都不能为 null // 确保 fast 每次都能移动两步 while (fast != null && fast.next != null) { slow = slow.next; // 慢指针走一步 fast = fast.next.next; // 快指针走两步 if (slow == fast) { // 如果相遇，则存在环 return true; } } return false; // 快指针到达末尾，没有环}
```
- 复杂度分析：
  - 时间复杂度：O(N)。快慢指针都在链表中移动，最坏情况下，快指针可能要遍历环两圈才能追上慢指针。
  - 空间复杂度：O(1)。只使用了常数个额外指针。
进阶：找到环的入口点

如果链表有环，如何找到环的入口点？
1. 当快慢指针相遇时，将快指针重新指向链表头（head）。
2. 然后，快慢指针以相同的速度（都一步一步）继续前进。
3. 它们再次相遇的节点，就是环的入口点。
- 数学证明（简述）：
  
  设：
  - 非环部分的长度为 A。
  - 环的长度为 B。
  - 慢指针在环内走的距离为 x。
  - 快指针在环内走的距离为 y。
  - 相遇时，慢指针走的距离为 A+x。
  - 快指针走的距离为 A+y。
    
    因为快指针速度是慢指针的两倍，所以 A+y=2(A+x)。
    
    又因为快慢指针都在环内移动，所以它们相遇时，快指针一定比慢指针多走了整数倍的环长，即 y−x=ktimesB (其中 k 是整数)。
    
    联立两式可推导出 A=(k−1)B+x。
    
    这意味着，从链表头走到环入口的距离 A，等于从相遇点继续走 k−1 圈环再走 x 的距离。也就是说，从 head 重新走，和从相遇点继续走，它们会在环入口处再次相遇。
- 代码实现：
  
  C#
```
public ListNode DetectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // 快慢指针相遇，有环 // 找到相遇点后，将其中一个指针（例如 fast）重新指向链表头 fast = head; // 然后 slow 和 fast 以相同速度前进，直到再次相遇 while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; // 再次相遇点就是环的入口 } } return null; // 没有环}
```
思考： 弗洛伊德判圈算法是快慢指针在链表问题中的一个高峰，能够判断环的存在并找到环的入口，非常强大且常用。

5. 链表相交 (Intersection of Two Linked Lists)

题目描述：

给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

示例：

输入：

listA = [4, 1, 8, 4, 5]

listB = [5, 6, 1, 8, 4, 5]

skipA = 2, skipB = 3 (表示第一个相交节点在 listA 中是索引 2，listB 中是索引 3)

输出：Reference of the node with value = 8 (即节点 8 是相交点)
解题思路：双指针 (走完各自的路，再走对方的路)

这是一个非常巧妙的思路。我们让两个指针 pA 和 pB 分别从 headA 和 headB 开始遍历。

当 pA 遍历完 listA 后，它转向 headB 继续遍历。

当 pB 遍历完 listB 后，它转向 headA 继续遍历。

核心思想：

如果两个链表相交，那么它们从相交点到末尾的公共部分是相同的。

设 listA 的长度为 L_A，listB 的长度为 L_B，公共部分的长度为 C。

那么 listA 的非公共部分长度为 L_A−C。

listB 的非公共部分长度为 L_B−C。
- pA 走过的总距离：($L_A - C$) + $C$ + ($L_B - C$)
- pB 走过的总距离：($L_B - C$) + $C$ + ($L_A - C$)
你会发现，如果它们相交，它们走的总距离是一样的！当它们走完 (L_A - C) + (L_B - C) 步后，如果相交，它们就会在相交点相遇。

如果它们不相交，它们最终都会走到 null，并在 null 处相遇（即都为 null）。

步骤：
1. 初始化 pA = headA, pB = headB。
2. 循环直到 pA == pB：
  
  a. 如果 pA 不为 null，pA 移动到 pA.next。
  
  b. 如果 pA 为 null，则将 pA 指向 headB。
  
  c. 如果 pB 不为 null，pB 移动到 pB.next。
  
  d. 如果 pB 为 null，则将 pB 指向 headA。
3. 循环结束时，pA（或 pB）就是相交点（如果相交），否则为 null。
- 代码实现：
  
  C#
```
public ListNode GetIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode pA = headA; ListNode pB = headB; // 循环直到 pA == pB // 情况1: 相交链表，最终会在交点相遇 // 情况2: 不相交链表，最终 pA 和 pB 都会变为 null，然后相等，退出循环 while (pA != pB) { // 如果 pA 走到链表 A 的末尾，则转向链表 B 的头 pA = (pA == null) ? headB : pA.next; // 如果 pB 走到链表 B 的末尾，则转向链表 A 的头 pB = (pB == null) ? headA : pB.next; } return pA; // 此时 pA (或 pB) 就是相交点，如果不相交则为 null}
```
- 复杂度分析：
  - 时间复杂度：O(M+N)，其中 M 和 N 是两个链表的长度。两个指针最多都走了 M+N 步。
  - 空间复杂度：O(1)。只使用了常数个额外指针。
思考： 这个题目展示了双指针在处理链表长度不一致时的巧妙应用。理解其“路程相等”的原理是关键。

总结与练习

本篇我们深入学习了链表这种重要的非连续存储数据结构。我们了解了单链表和双链表的结构，特别是 ListNode 的定义和虚拟头结点的妙用。我们还掌握了链表最基本的操作：遍历、查找、插入和删除。

最重要的是，我们通过五个经典的面试题目，深入理解了指针的艺术和快慢指针在链表问题中的强大作用：

反转链表：掌握迭代法（三指针法）和递归法，这是链表操作的基石。
合并两个有序链表：利用虚拟头结点和双指针高效合并。
删除链表的倒数第 N 个结点：通过快慢指针精确定位。
环形链表：用快慢指针（龟兔赛跑算法）判断环的存在和找出环的入口。
链表相交：巧妙的双指针技巧，让两个指针走等长路径以找到相交点。

本篇核心知识点回顾：

链表与数组的区别：连续/离散存储，随机访问/顺序访问，插入删除效率。
ListNode 结构：val 和 next。
虚拟头结点（Dummy Node）：简化链表头部操作。
链表基本操作：遍历、插入、删除。
反转链表（迭代/递归）：理解指针的翻转逻辑。
快慢指针：在链表中用于定位（中间节点、倒数第N个）、判断环、找环入口等。
双指针（走各自的路）：解决链表相交问题。

课后练习（推荐力扣 LeetCode 题目）：

反转链表 (Reverse Linked List)：LeetCode 206
合并两个有序链表 (Merge Two Sorted Lists)：LeetCode 21
删除链表的倒数第 N 个结点 (Remove Nth Node From End of List)：LeetCode 19
环形链表 (Linked List Cycle)：LeetCode 141
环形链表 II (Linked List Cycle II)：LeetCode 142 (找到环的入口)
链表相交 (Intersection of Two Linked Lists)：LeetCode 160
删除排序链表中的重复元素 (Remove Duplicates from Sorted List)：LeetCode 83 (简单双指针)
对链表进行插入排序 (Insertion Sort List)：LeetCode 147 (挑战题，将链表和排序结合)

熟练掌握这些链表问题，特别是快慢指针的运用，将极大地提升你在面试中的表现。它们是理解更复杂数据结构和算法（如树、图）的重要铺垫。

算法入门第二篇：链表的艺术：结构、操作与指针魔法

引言：链表为何如此重要？

链表基础：节点与结构

单链表（Singly Linked List）

双链表（Doubly Linked List）

基本操作

经典面试题与解法：链表篇

1. 反转链表 (Reverse Linked List)

2. 合并两个有序链表 (Merge Two Sorted Lists)

3. 删除链表的倒数第 N 个结点 (Remove Nth Node From End of List)

4. 环形链表 (Linked List Cycle)

5. 链表相交 (Intersection of Two Linked Lists)

总结与练习

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

标签

算法入门第二篇：链表的艺术：结构、操作与指针魔法

引言：链表为何如此重要？

链表基础：节点与结构

单链表（Singly Linked List）

双链表（Doubly Linked List）

基本操作

经典面试题与解法：链表篇

1. 反转链表 (Reverse Linked List)

2. 合并两个有序链表 (Merge Two Sorted Lists)

3. 删除链表的倒数第 N 个结点 (Remove Nth Node From End of List)

4. 环形链表 (Linked List Cycle)

5. 链表相交 (Intersection of Two Linked Lists)

总结与练习

相关问题

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

标签