链表基础与 LeetCode 练习

一、链表概念#

与数组的区别
- 数组：连续内存空间，随机访问高效（O(1)），但插入/删除需移动元素（O(n)）
- 链表：节点离散存储，通过指针连接（逻辑连续，物理非连续）
- 访问效率：链表只能顺序访问（O(n)），但插入/删除只需修改指针（O(1)）
节点结构（C++实现）

1
struct ListNode {
2
    int val;         // 存储数据
3
    ListNode* next;  // 指向下一节点的指针
4
    ListNode(int x) : val(x), next(nullptr) {}
5
};

二、链表底层机制#

内存分配原理
- 节点内存非连续 → 动态分配（C++用new/delete）
- 创建节点：ListNode* node = new ListNode(10);
- 释放节点：delete node;（避免内存泄漏）
指针操作图解

1
初始： head → A → B → C → nullptr
2
删除B：
3
  1. 定位A: A->next = B->next
4
  2. 释放B: delete B
5
结果： head → A → C → nullptr

三、链表五大基础操作（C++实现）#

1. 遍历链表#

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

2. 插入节点#

头部插入

1
void insertAtHead(ListNode*& head, int val) {
2
    ListNode* newNode = new ListNode(val);
3
    newNode->next = head;
4
    head = newNode;
5
}

尾部插入

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

中间插入（在pos节点后插入）

1
void insertAfter(ListNode* pos, int val) {
2
    if (pos == nullptr) return;
3
    ListNode* newNode = new ListNode(val);
4
    newNode->next = pos->next;
5
    pos->next = newNode;
6
}

3. 删除节点#

1
void deleteNode(ListNode*& head, int val) {
2
    if (head == nullptr) return;
3

4
    if (head->val == val) {
5
        ListNode* temp = head;
6
        head = head->next;
7
        delete temp;
8
        return;
9
    }
10

11
    ListNode* cur = head;
12
    while (cur->next != nullptr && cur->next->val != val) {
13
        cur = cur->next;
14
    }
15

16
    if (cur->next != nullptr) {
17
        ListNode* temp = cur->next;
18
        cur->next = cur->next->next;
19
        delete temp;
20
    }
21
}

4. 修改节点值#

1
void updateNode(ListNode* head, int oldVal, int newVal) {
2
    ListNode* cur = head;
3
    while (cur != nullptr) {
4
        if (cur->val == oldVal) {
5
            cur->val = newVal;
6
            return;
7
        }
8
        cur = cur->next;
9
    }
10
}

5. 查找节点#

1
ListNode* searchNode(ListNode* head, int val) {
2
    ListNode* cur = head;
3
    while (cur != nullptr) {
4
        if (cur->val == val) {
5
            return cur;
6
        }
7
        cur = cur->next;
8
    }
9
    return nullptr;
10
}

四、关键点#

头指针的特殊处理
- 头节点可能被修改 → 使用ListNode*&（指针引用）或二级指针
- 空链表判断：if (head == nullptr)
边界条件检查
- 插入/删除头节点
- 操作空链表
- 处理尾节点（next指向nullptr）
内存管理要点
- 每次new后必须对应delete
- 删除节点时需先保存下一节点指针
哨兵节点技巧（简化操作）

1
ListNode* dummy = new ListNode(0);
2
dummy->next = head;
3
// ...执行操作...
4
head = dummy->next;
5
delete dummy;

五、链表 vs 数组#

特性	数组	链表
内存连续性	连续	非连续
访问方式	O(1)随机访问	O(n)顺序访问
插入/删除成本	O(n)需要移动元素	O(1)修改指针
扩容	需重新分配内存	动态增加节点
头部插入	O(n)	O(1)
局部性原理	优	差

六、LeetCode 练习#

1. 删除链表中的节点（LeetCode 237）#

问题本质：在只给定被删除节点（非尾节点）的情况下，实现节点删除

1
void deleteNode(struct ListNode* node) {
2
    node->val = node->next->val;
3
    node->next = node->next->next;
4
}

要点：

无法访问前驱节点，因此采用”值替换+跳过”策略
时间复杂度 O(1)，空间复杂度 O(1)
特例处理：不能删除尾节点（题目保证）

2. 反转链表（LeetCode 206）#

迭代法：

反转链表图解

1
class Solution {
2
public:
3
    ListNode* reverseList(ListNode* head) {
4
        ListNode *cur = head, *pre = nullptr;
5
        while(cur != nullptr) {
6
            ListNode* tmp = cur->next;
7
            cur->next = pre;
8
            pre = cur;
9
            cur = tmp;
10
        }
11
        return pre;
12
    }
13
};

迭代步骤详解（每轮循环的指针状态变化）：

步骤	状态描述	图示
1	cur=1, tmp=2, pre=null，反转 1→null
2	pre=cur 进行中，准备进入下一步
3	pre=1, cur=2, tmp=3，1→null 已反转
4	pre=cur 进行中，准备进入下一步
5	pre=2, cur=3, tmp=4，2→1→null
6	pre=cur 进行中，准备进入下一步
7	pre=3, cur=4, tmp=5，3→2→1→null
8	pre=cur 进行中，准备进入下一步
9	pre=4, cur=5, tmp=null，4→3→2→1→null
10	pre=cur 进行中，准备进入下一步
11	循环结束：5→4→3→2→1→null，返回 pre

递归法：

1
class Solution {
2
public:
3
    ListNode* reverseList(ListNode* head) {
4
        return recur(head, nullptr);
5
    }
6
private:
7
    ListNode* recur(ListNode* cur, ListNode* pre) {
8
        if (cur == nullptr) return pre;
9
        ListNode* res = recur(cur->next, cur);
10
        cur->next = pre;
11
        return res;
12
    }
13
};

方法	时间复杂度	空间复杂度	适用场景
迭代法	O(n)	O(1)	内存敏感场景
递归法	O(n)	O(n)	代码简洁要求场景

3. 设计链表（LeetCode 707）#

双向链表实现框架：

1
typedef struct MyLinkedListNode {
2
    int val;
3
    struct MyLinkedListNode *prev;
4
    struct MyLinkedListNode *next;
5
} Node;
6

7
typedef struct {
8
    Node *head;
9
    Node *tail;
10
    int size;
11
} MyLinkedList;

设计原则：

虚拟头尾节点：统一处理边界情况
size维护：避免多余遍历
指针安全：每次操作前检查NULL

4. K 个一组翻转链表（LeetCode 25）#

问题描述：给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

K个一组翻转图解

1
原始链表：1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9
2
按 k=4 分组：
3
  组1: 1 → 2 → 3 → 4
4
  组2: 5 → 6 → 7 → 8 → 9 (剩余不足 4 个，保持原序)
5

6
翻转后：4 → 3 → 2 → 1 → 5 → 6 → 7 → 8 → 9

1
class Solution {
2
public:
3
    // 翻转 [a, b) 区间内的链表节点（不包含 b）
4
    ListNode* reverse(ListNode* a, ListNode* b) {
5
        ListNode *pre = nullptr, *cur = a, *next;
6
        while (cur != b) {
7
            next = cur->next;
8
            cur->next = pre;
9
            pre = cur;
10
            cur = next;
11
        }
12
        return pre;  // 返回翻转后的新头
13
    }
14

15
    ListNode* reverseKGroup(ListNode* head, int k) {
16
        if (head == nullptr) return nullptr;
17

18
        ListNode *a = head, *b = head;
19
        // 前进 k 步，找到本组尾部
20
        for (int i = 0; i < k; i++) {
21
            if (b == nullptr) return head;  // 不足 k 个，保持原序
22
            b = b->next;
23
        }
24

25
        // 翻转前 k 个
26
        ListNode* newHead = reverse(a, b);
27
        // 递归处理后续链表
28
        a->next = reverseKGroup(b, k);
29
        return newHead;
30
    }
31
};

关键点：

使用 [a, b) 半开区间翻转，避免对尾节点做特殊处理
递归处理后续分组，每次处理 k 个节点
不足 k 个的剩余节点保持原序（不翻转）
时间复杂度 O(n)，空间复杂度 O(n/k) 的递归栈