

链表是**线性数据结构**，但与数组有本质区别。数组是连续的内存空间，支持随机访问；链表则是**离散的内存节点通过指针连接**，只支持顺序访问。理解链表的核心在于掌握**指针操作**和**节点关系管理**。

## 一、单链表基础：节点结构与创建

### 1.1 单链表节点结构

```cpp
struct ListNode {
    int val;         // 节点值
    ListNode* next;  // 指向下一个节点的指针
    
    ListNode(int x) : val(x), next(nullptr) {}
};
```

**关键理解**：
- 每个节点包含两部分：数据域(val)和指针域(next)
- `next`指针指向下一个节点，形成链式结构
- 最后一个节点的`next`指向`nullptr`，表示链表结束

### 1.2 创建链表的三种方法

#### 方法一：手动连接
```cpp
// 创建三个节点
ListNode* node1 = new ListNode(1);
ListNode* node2 = new ListNode(2);
ListNode* node3 = new ListNode(3);

// 手动连接
node1->next = node2;
node2->next = node3;
// node3->next 保持为 nullptr
```

#### 方法二：尾插法（最常用）
```cpp
ListNode* createList(const vector<int>& nums) {
    ListNode dummy(0);  // 哑节点，简化边界处理
    ListNode* tail = &dummy;  // 尾指针，始终指向最后一个节点
    
    for (int num : nums) {
        tail->next = new ListNode(num);
        tail = tail->next;  // 移动尾指针
    }
    
    return dummy.next;  // 返回真正的头节点
}
```

**哑节点技巧**：
- 避免处理头节点的特殊情况
- 代码更简洁，逻辑更清晰
- 常用在链表操作中

#### 方法三：头插法（创建逆序链表）
```cpp
ListNode* createReverseList(const vector<int>& nums) {
    ListNode* head = nullptr;
    
    for (int num : nums) {
        ListNode* newNode = new ListNode(num);
        newNode->next = head;  // 新节点指向原头节点
        head = newNode;        // 更新头节点
    }
    
    return head;
}
```

### 1.3 遍历链表

```cpp
void printList(ListNode* head) {
    ListNode* curr = head;
    
    while (curr) {
        cout << curr->val;
        if (curr->next) cout << " -> ";
        curr = curr->next;
    }
    cout << " -> nullptr" << endl;
}
```

## 二、单链表核心操作：反转算法详解

### 2.1 问题分析：为什么要反转链表？

链表反转是**最经典的链表问题**，考察对指针操作的理解。反转意味着改变节点间的指向关系，将`a->b->c`变为`a<-b<-c`。

### 2.2 迭代反转法（三指针法）

```cpp
ListNode* reverseIterative(ListNode* head) {
    ListNode* prev = nullptr;   // 前一个节点，初始为nullptr
    ListNode* curr = head;      // 当前节点，从头节点开始
    ListNode* next = nullptr;   // 下一个节点，临时保存
    
    while (curr) {
        // 步骤1：保存下一个节点（关键！）
        next = curr->next;
        
        // 步骤2：反转当前节点的指针
        curr->next = prev;
        
        // 步骤3：移动指针，准备下一次循环
        prev = curr;  // prev移动到当前节点
        curr = next;  // curr移动到下一个节点
    }
    
    return prev;  // 循环结束时，prev指向原链表的尾节点，即新链表的头节点
}
```

#### 逐步分析（链表：1->2->3->nullptr）

```
初始状态：
prev = nullptr
curr = 1
next = nullptr

第1次循环：
next = curr->next = 2        // 保存节点2
curr->next = prev = nullptr  // 1->nullptr
prev = curr = 1              // prev指向1
curr = next = 2              // curr指向2
结果：nullptr <- 1   2->3->nullptr

第2次循环：
next = curr->next = 3        // 保存节点3
curr->next = prev = 1        // 2->1
prev = curr = 2              // prev指向2
curr = next = 3              // curr指向3
结果：nullptr <- 1 <- 2   3->nullptr

第3次循环：
next = curr->next = nullptr  // 保存nullptr
curr->next = prev = 2        // 3->2
prev = curr = 3              // prev指向3
curr = next = nullptr        // curr指向nullptr，循环结束
结果：nullptr <- 1 <- 2 <- 3

返回prev = 3，即新链表的头节点
```

### 2.3 为什么这个算法正确？

1. **保存next是必须的**：一旦执行`curr->next = prev`，就丢失了原链表的下一个节点
2. **移动指针的顺序**：必须先移动prev到curr，再移动curr到next
3. **终止条件**：当curr为nullptr时，prev指向原链表的最后一个节点，即新链表的第一个节点

### 2.4 递归反转法

```cpp
ListNode* reverseRecursive(ListNode* head) {
    // 递归终止条件：空链表或单个节点
    if (!head || !head->next) {
        return head;
    }
    
    // 递归反转剩余部分
    ListNode* newHead = reverseRecursive(head->next);
    
    // 关键操作：让下一个节点指向自己
    head->next->next = head;
    // 断开自己的next指针（否则会成环）
    head->next = nullptr;
    
    return newHead;
}
```

#### 递归深度分析（链表：1->2->3）

```
调用栈：
reverse(1)
  reverse(2)
    reverse(3) -> 返回3
    
reverse(2)层：
  newHead = 3
  2->3->2（形成环）
  2->next = nullptr
  返回3->2
    
reverse(1)层：
  newHead = 3->2
  1->2->1（形成环）
  1->next = nullptr
  返回3->2->1
```

### 2.5 使用栈辅助反转（理解用）

```cpp
ListNode* reverseWithStack(ListNode* head) {
    if (!head) return nullptr;
    
    stack<ListNode*> st;
    ListNode* curr = head;
    
    // 所有节点入栈
    while (curr) {
        st.push(curr);
        curr = curr->next;
    }
    
    // 栈顶是原链表的尾节点，作为新链表的头
    ListNode* newHead = st.top();
    st.pop();
    curr = newHead;
    
    // 依次出栈并连接
    while (!st.empty()) {
        curr->next = st.top();
        st.pop();
        curr = curr->next;
    }
    
    // 关键：最后一个节点的next置空
    curr->next = nullptr;
    
    return newHead;
}
```

**缺点**：需要O(n)额外空间，效率不如迭代法

## 三、双链表详解：双向关系管理

### 3.1 双链表节点结构

```cpp
struct DListNode {
    int val;
    DListNode* prev;  // 指向前一个节点
    DListNode* next;  // 指向后一个节点
    
    DListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};
```

**与单链表的区别**：
- 多了一个`prev`指针，指向前驱节点
- 可以双向遍历：从头到尾或从尾到头
- 删除操作更简单（不需要找到前驱节点）

### 3.2 双链表的优势与代价

**优势**：
1. 双向遍历：可以从任意节点向前或向后遍历
2. 删除操作简单：不需要寻找前驱节点
3. 某些操作更高效：如删除尾节点只需O(1)

**代价**：
1. 每个节点多一个指针，内存占用增加
2. 插入/删除时需要维护两个指针，代码稍复杂
3. 需要更多的指针操作，容易出错

### 3.3 双链表插入操作

#### 在头部插入
```cpp
void insertAtHead(DListNode*& head, DListNode*& tail, int val) {
    DListNode* newNode = new DListNode(val);
    
    if (!head) {  // 空链表
        head = tail = newNode;
    } else {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
}
```

#### 在尾部插入
```cpp
void insertAtTail(DListNode*& head, DListNode*& tail, int val) {
    DListNode* newNode = new DListNode(val);
    
    if (!tail) {  // 空链表
        head = tail = newNode;
    } else {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }
}
```

#### 在指定节点后插入
```cpp
void insertAfter(DListNode* node, int val) {
    if (!node) return;
    
    DListNode* newNode = new DListNode(val);
    
    // 连接新节点与后继节点
    newNode->next = node->next;
    if (node->next) {
        node->next->prev = newNode;
    }
    
    // 连接新节点与前驱节点
    newNode->prev = node;
    node->next = newNode;
}
```

### 3.4 双链表删除操作（重点）

#### 删除节点的三种情况

```cpp
void deleteNode(DListNode*& head, DListNode*& tail, DListNode* target) {
    if (!head || !target) return;  // 边界检查
    
    // 情况1：删除头节点
    if (target == head) {
        head = head->next;        // 头指针后移
        if (head) {
            head->prev = nullptr; // 新头节点的prev置空
        } else {
            tail = nullptr;       // 链表变空，尾指针也置空
        }
    }
    // 情况2：删除尾节点
    else if (target == tail) {
        tail = tail->prev;        // 尾指针前移
        if (tail) {
            tail->next = nullptr; // 新尾节点的next置空
        } else {
            head = nullptr;       // 链表变空，头指针也置空
        }
    }
    // 情况3：删除中间节点
    else {
        // 跳过要删除的节点
        target->prev->next = target->next;
        target->next->prev = target->prev;
    }
    
    delete target;  // 释放内存
}
```

#### 图解删除过程

```
删除中间节点B：A <-> B <-> C

步骤1：A->next = C
A <-> C  B <-> C

步骤2：C->prev = A
A <-> C  B孤立

步骤3：delete B
A <-> C
```

#### 删除操作的注意事项

1. **更新相邻节点的指针**：
   - 前驱节点的next指向后继节点
   - 后继节点的prev指向前驱节点

2. **处理边界情况**：
   - 删除头节点：更新head指针
   - 删除尾节点：更新tail指针
   - 删除唯一节点：head和tail都置空

3. **内存管理**：记得delete释放内存

### 3.5 按值删除

```cpp
void deleteByValue(DListNode*& head, DListNode*& tail, int val) {
    DListNode* curr = head;
    
    while (curr) {
        if (curr->val == val) {
            DListNode* toDelete = curr;
            curr = curr->next;  // 先移动到下一个节点
            
            deleteNode(head, tail, toDelete);
        } else {
            curr = curr->next;
        }
    }
}
```

**关键点**：在删除节点前，先保存下一个节点，否则删除后无法继续遍历。

## 四、链表排序：归并排序的实现

### 4.1 为什么链表排序用归并？

链表与数组不同：
1. **不支持随机访问**：不能像数组那样用下标直接访问任意元素
2. **移动元素代价低**：只需修改指针，不需要复制数据
3. **归并排序特点**：适合顺序访问的数据结构

### 4.2 归并排序的完整实现

#### 步骤1：找到中间节点（快慢指针）

```cpp
ListNode* getMiddle(ListNode* head) {
    if (!head) return nullptr;
    
    ListNode* slow = head;
    ListNode* fast = head->next;  // fast从head->next开始
    
    // fast走两步，slow走一步
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;  // slow指向中间节点
}
```

**为什么fast从head->next开始？**
- 对于偶数个节点：1->2->3->4
- fast从head开始：slow指向3（第二个中间节点）
- fast从head->next开始：slow指向2（第一个中间节点）
- 我们通常希望分割得尽量均匀

#### 步骤2：递归排序

```cpp
ListNode* mergeSort(ListNode* head) {
    // 递归终止条件：空链表或单个节点
    if (!head || !head->next) return head;
    
    // 1. 找到中间节点并分割
    ListNode* mid = getMiddle(head);
    ListNode* right = mid->next;
    mid->next = nullptr;  // 关键：切断链表
    
    // 2. 递归排序左右两部分
    ListNode* leftSorted = mergeSort(head);
    ListNode* rightSorted = mergeSort(right);
    
    // 3. 合并两个有序链表
    return merge(leftSorted, rightSorted);
}
```

#### 步骤3：合并有序链表

```cpp
ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);  // 哑节点，简化操作
    ListNode* tail = &dummy;
    
    // 比较两个链表的头节点，选择较小的
    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    // 连接剩余部分
    tail->next = l1 ? l1 : l2;
    
    return dummy.next;
}
```

### 4.3 时间复杂度分析

1. **分割阶段**：
   - 每次分割需要找到中间节点：O(n)
   - 共分割log₂n次
   - 总分割时间：O(n log n)

2. **合并阶段**：
   - 每次合并需要遍历所有节点：O(n)
   - 共合并log₂n次
   - 总合并时间：O(n log n)

**总时间复杂度**：O(n log n)

**空间复杂度**：
- 递归栈深度：O(log n)
- 不需要额外数组：O(1)额外空间

### 4.4 归并排序的变种：自底向上

```cpp
ListNode* mergeSortBottomUp(ListNode* head) {
    if (!head || !head->next) return head;
    
    // 1. 计算链表长度
    int length = 0;
    ListNode* curr = head;
    while (curr) {
        length++;
        curr = curr->next;
    }
    
    ListNode dummy(0);
    dummy.next = head;
    
    // 2. 从1开始，每次合并相邻的子链表
    for (int step = 1; step < length; step *= 2) {
        ListNode* prev = &dummy;
        ListNode* curr = dummy.next;
        
        while (curr) {
            // 获取第一个子链表
            ListNode* left = curr;
            for (int i = 1; i < step && curr->next; i++) {
                curr = curr->next;
            }
            
            // 获取第二个子链表
            ListNode* right = curr->next;
            curr->next = nullptr;  // 断开第一个子链表
            curr = right;
            
            for (int i = 1; i < step && curr && curr->next; i++) {
                curr = curr->next;
            }
            
            // 保存下一个子链表的起始位置
            ListNode* next = nullptr;
            if (curr) {
                next = curr->next;
                curr->next = nullptr;  // 断开第二个子链表
            }
            
            // 合并两个子链表
            ListNode* merged = merge(left, right);
            
            // 连接到已合并的部分
            prev->next = merged;
            while (prev->next) {
                prev = prev->next;
            }
            
            // 继续处理剩余部分
            curr = next;
        }
    }
    
    return dummy.next;
}
```

**优点**：避免递归，空间复杂度O(1)

## 五、链表常见问题与解决方案

### 5.1 检测环（快慢指针）

```cpp
bool hasCycle(ListNode* head) {
    if (!head || !head->next) return false;
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;        // 慢指针走一步
        fast = fast->next->next;  // 快指针走两步
        
        if (slow == fast) {
            return true;  // 相遇说明有环
        }
    }
    
    return false;  // 快指针到达nullptr，说明无环
}
```

### 5.2 找到环的入口

```cpp
ListNode* detectCycle(ListNode* head) {
    if (!head || !head->next) return nullptr;
    
    ListNode* slow = head;
    ListNode* fast = head;
    bool hasCycle = false;
    
    // 第一步：判断是否有环
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }
    
    if (!hasCycle) return nullptr;
    
    // 第二步：找到环的入口
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    
    return slow;
}
```

**原理**（Floyd判圈算法）：
1. 设头节点到环入口距离为a，环长度为b
2. 第一次相遇时，慢指针走了a + x，快指针走了a + x + nb
3. 由快指针速度是慢指针两倍：2(a + x) = a + x + nb
4. 得到：a = (n-1)b + (b - x)
5. 让一个指针从head开始，一个从相遇点开始，每次走一步，相遇点就是环入口

### 5.3 找到倒数第k个节点

```cpp
ListNode* findKthFromEnd(ListNode* head, int k) {
    if (!head || k <= 0) return nullptr;
    
    ListNode* fast = head;
    ListNode* slow = head;
    
    // fast先走k步
    for (int i = 0; i < k; i++) {
        if (!fast) return nullptr;  // k大于链表长度
        fast = fast->next;
    }
    
    // fast和slow一起走
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }
    
    return slow;
}
```

### 5.4 删除重复节点

```cpp
// 删除排序链表中的重复元素
ListNode* deleteDuplicates(ListNode* head) {
    if (!head) return nullptr;
    
    ListNode* curr = head;
    
    while (curr && curr->next) {
        if (curr->val == curr->next->val) {
            ListNode* toDelete = curr->next;
            curr->next = curr->next->next;
            delete toDelete;
        } else {
            curr = curr->next;
        }
    }
    
    return head;
}
```

## 六、链表操作的常见错误

### 6.1 指针未初始化

```cpp
// 错误
ListNode* ptr;
cout << ptr->val;  // 访问随机内存，段错误

// 正确
ListNode* ptr = nullptr;  // 或 = new ListNode(0)
```

### 6.2 访问已释放的内存

```cpp
ListNode* node = new ListNode(1);
delete node;
cout << node->val;  // 错误：访问已释放的内存
```

### 6.3 忘记断开连接（形成环）

```cpp
// 反转链表时忘记断开原连接
ListNode* newHead = reverse(head);
// 如果原链表没有正确断开，可能形成环
```

### 6.4 丢失头指针

```cpp
ListNode* head = new ListNode(1);
head = head->next;  // 丢失了原头节点，内存泄漏
```

## 七、链表与数组的对比

| 特性 | 数组 | 链表 |
|------|------|------|
| **内存分配** | 连续 | 离散 |
| **访问方式** | 随机访问 | 顺序访问 |
| **访问时间** | O(1) | O(n) |
| **插入/删除** | O(n) | O(1)（已知位置） |
| **内存使用** | 固定大小 | 动态增长 |
| **缓存友好** | 是 | 否 |

**选择原则**：
- 需要快速随机访问 → 数组
- 需要频繁插入/删除 → 链表
- 内存使用不确定 → 链表
- 需要缓存友好 → 数组

链表操作的核心是**理解指针关系**和**管理内存生命周期**。掌握链表的基础操作后，复杂问题往往是这些基础操作的组合。多练习、多思考，才能真正掌握链表的精髓。

链表是线性数据结构，但与数组有本质区别。数组是连续的内存空间，支持随机访问；链表则是离散的内存节点通过指针连接，只支持顺序访问。理解链表的核心在于掌握指针操作和节点关系管理。

单链表与双链表专题详解

高级软件开发工程师

编程语言

算法

后端

链表是重要的线性数据结构，通过指针连接离散节点。本文详解单双链表结构、创建方法、反转算法、排序实现及常见问题解决方案，对比链表与数组特性差异，帮助开发者掌握指针操作和节点关系管理，提升算法能力。

数据结构

内存管理

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

单链表与双链表专题详解-腾讯云开发者社区-腾讯云

单链表与双链表专题详解

单链表与双链表专题详解

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐