2025-12-27-算法刷题-关于链表操作

后悔数据结构当初没有好好学的第n天现在恶补，知识学爆

基础操作：

查找元素：根据值查找节点位置
指定位置插入：在特定位置插入新节点
指定位置获取：获取特定位置的节点值
指定位置删除：删除特定位置的节点
获取长度：统计链表中节点的数量

	题目描述	主要实现思路
BM1	反转链表	使用三指针（prev、curr、next）迭代反转：保存下一个节点，反转当前指向，移动指针。返回prev作为新头。
BM2	链表内指定区间反转	引入虚拟头结点定位第m-1个节点（pre）。然后在[m,n]区间执行(n-m)次头插法（逐个将下一个节点插入pre后）。
BM3	链表中的节点每k个一组翻转	每k个节点为一组，使用反转链表方法局部反转。若剩余不足k个，则保持原序。递归或迭代均可，推荐迭代分段处理。
BM4	合并两个排序的链表	双指针模拟归并排序：比较两个链表当前节点值，小者接入新链表，移动对应指针。处理剩余部分。
BM5	合并k个已排序的链表	使用小根堆（优先队列）维护k个链表头结点，每次弹出最小值并接入结果链表，同时推入其下一个节点。
BM6	判断链表中是否有环	快慢指针（Floyd判圈算法）：fast每次走2步，slow走1步。若相遇则有环，否则无环。
BM7	链表中环的入口结点	先用快慢指针相遇于环内某点，再令一指针从头启动，与慢指针同步移动，相遇处即环入口。
BM8	链表中倒数最后k个结点	快慢指针：fast先走k步，然后slow与fast同步移动，至fast到尾时slow即为倒数第k个节点。
BM9	删除链表的倒数第n个节点	同BM8定位倒数第n+1个节点（pre），然后pre.next = pre.next.next删除目标节点。注意头节点特殊处理。
BM10	两个链表的第一个公共结点	双指针同步走：先计算长度差，长者先走差值步；或让指针走完一链表后换另一链表，总路程相等时相遇即公共节点。
BM11	链表相加(二)	模拟加法从低位到高位（需先反转链表或用栈），处理进位。结果可能需反转回原序。
BM12	单链表的排序	归并排序（自底向上）：分段合并有序子链表，或快慢指针找中点递归归并。时间O(n log n)。
BM13	判断一个链表是否为回文结构	快慢指针找中点，反转后半部分，与前半部分逐节点比较值是否相等。恢复链表可选。
BM14	链表的奇偶重排	分离奇偶位节点成两个链表（odd、even），然后even接odd尾部。注意偶数长度处理。
BM15	删除有序链表中重复的元素-I	单指针遍历：若当前节点与下一节点值相同，跳过下一节点（保留首次出现）。
BM16	删除有序链表中重复的元素-II	引入虚拟头结点，双指针或单指针遍历：若连续重复，跳过整个重复段（一个不留）。

一般会给出一个最基础的链表

1
function ListNode(val, next) {
2
    this.val = (val === undefined ? 0 : val);
3
    this.next = (next === undefined ? null : next);
4
}

节点包含两个成员：
- val：存储节点的值，通常为整数（int），题目中 |val| ≤ 1000。
- next：指向下一个节点的指针（引用），类型为同类 ListNode*（或 ListNode），初始可能为 NULL/null/None
无哑头节点（dummy head）：输入的 head 就是真实头结点（有有效值），除非题目特别说明
单向链表：只能从头到尾遍历，无前向指针
输入形式：
- 函数签名通常为 ListNode* head（或类似），可能额外传入其他参数（如 m、n、k 等）
- 空链表：head = NULL / null / None
输出形式：
- 大多数题目要求返回新的头结点（ListNode*）
- 操作通常要求原地修改，以满足空间复杂度 O(1)

常见操作#

单链表常见操作的实现方法#

以下针对单链表（节点结构为 val 和 next）的几种常见操作，提供标准、高效的实现思路。所有操作均基于从头结点开始遍历，时间复杂度与空间复杂度分析清晰。假设节点定义如下（以 JavaScript 为例，其他语言类似）：

1
function ListNode(val, next) {
2
    this.val = val;
3
    this.next = next || null;
4
}

1. 查找元素：根据值查找节点位置（返回位置或节点）#

思路：从头遍历，逐个比较节点值，直到找到匹配值或到达链表末尾。

实现要点：

返回第一个匹配节点的位置（从 1 开始）或节点本身。
未找到返回 -1 或 null。

1
function findNode(head, target) {
2
    let pos = 1;
3
    let curr = head;
4
    while (curr !== null) {
5
        if (curr.val === target) {
6
            return pos;  // 或 return curr; 返回节点本身
7
        }
8
        curr = curr.next;
9
        pos++;
10
    }
11
    return -1;  // 未找到
12
}

时间复杂度：O(n)
空间复杂度：O(1)

2. 指定位置插入：在第 i 个位置插入新节点（i 从 1 开始）#

思路：遍历到第 i-1 个节点，将新节点插入其后。特殊处理插入到头部（i=1）。

实现要点：

若 i=1，新节点成为新头。
若 i > 长度，插入失败或插入尾部（视题目要求）。

1
function insertAtPosition(head, i, val) {
2
    let newNode = new ListNode(val);
3
    if (i === 1) {
4
        newNode.next = head;
5
        return newNode;  // 新头结点
6
    }
7

8
    let curr = head;
9
    for (let pos = 1; pos < i - 1 && curr !== null; pos++) {
10
        curr = curr.next;
11
    }
12
    if (curr === null) return head;  // i 超出范围，不插入
13

14
    newNode.next = curr.next;
15
    curr.next = newNode;
16
    return head;
17
}

时间复杂度：O(i) → 最坏 O(n)
空间复杂度：O(1)

3. 指定位置获取：获取第 i 个节点的値（i 从 1 开始）#

思路：遍历 i-1 步，直接返回当前节点的值。

1
function getAtPosition(head, i) {
2
    let curr = head;
3
    for (let pos = 1; pos < i && curr !== null; pos++) {
4
        curr = curr.next;
5
    }
6
    return curr ? curr.val : null;  // 未找到返回 null
7
}

时间复杂度：O(i) → 最坏 O(n)
空间复杂度：O(1)

4. 指定位置删除：删除第 i 个节点（i 从 1 开始）#

思路：遍历到第 i-1 个节点，修改其 next 指向跳过第 i 个节点。特殊处理删除头结点。

1
function deleteAtPosition(head, i) {
2
    if (head === null) return null;
3
    if (i === 1) return head.next;  // 删除头结点
4

5
    let curr = head;
6
    for (let pos = 1; pos < i - 1 && curr !== null; pos++) {
7
        curr = curr.next;
8
    }
9
    if (curr === null || curr.next === null) return head;  // i 超出范围
10

11
    curr.next = curr.next.next;  // 跳过第 i 个节点
12
    return head;
13
}

时间复杂度：O(i) → 最坏 O(n)
空间复杂度：O(1)

5. 获取链表长度（节点数量）#

思路：遍历链表，累计计数。

1
function getLength(head) {
2
    let len = 0;
3
    let curr = head;
4
    while (curr !== null) {
5
        len++;
6
        curr = curr.next;
7
    }
8
    return len;
9
}

时间复杂度：O(n)
空间复杂度：O(1)

反转链表#

BM1 | 全量反转链表#

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤10000≤n≤1000

要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

解法：

初始化 prev 为 null（新链表的尾部）。
current 从链表头节点开始。
在循环中：
- 暂存 next = current.next（避免指针丢失）。
- 将 current.next 指向 prev（反转当前指针）。
- 更新 prev = current（前移 prev）。
- 更新 current = next（前移 current）。
循环结束后，prev 指向原链表的尾节点（新头节点），更新 list.head = prev。

其实就是三指针原地反转

1
export function ReverseList(head: ListNode): ListNode {
2
    let prev = null;
3
    let curr = head;
4

5
    while (curr !== null) {
6

7
        // 保存下一个节点，防止断链
8
        let next = curr.next;
9

10
        // 反转当前节点的指向
11
        curr.next = prev;
12

13
        // 指针向前移动
14
        prev = curr;
15
        curr = next;
16
    }
17
    // prev 指向反转后的新头结点
18
    return prev;
19
};

BM2 | 反转链表部分区间#

给定一个单链表的头结点 head，长度为 n，反转该链表从位置 m 到 n 的部分，返回反转后的链表。

数据范围： 0≤m≤n≤n≤1000 ，链表中任意节点的值满足 |val|≤1000

例如：
给出的链表为 1→2→3→4→5→NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4,
返回 1→4→3→2→5→NULL1→4→3→2→5→NULL.

要实现原地反转指定区间，需要：

找到反转区间的前一个节点（pre），即第 m-1 个节点。
找到反转区间的最后一个节点（记为 end），即第 n 个节点。
将 [m, n] 区间使用经典链表反转方法进行原地反转。
正确连接反转后的区间与前后部分：
- pre.next 指向反转后区间的新的头节点（原第 n 个节点）。
- 反转后区间的尾节点（原第 m 个节点）指向 end.next。

关键操作：

先遍历定位到 pre 和反转区间的起始节点 start（第 m 个节点）。
然后在 [start, end] 区间内使用三指针迭代反转。
最后调整指针连接。

1
export function reverseBetween(head: ListNode | null, m: number, n: number): ListNode | null {
2
    if (head === null || m === n) return head;
3

4
    const dummy = new ListNode(0);
5
    dummy.next = head;
6
    let pre = dummy;
7

8
    // 移动到第 m-1 个节点
9
    for (let i = 0; i < m - 1; i++) {
10
        pre = pre.next!;
11
    }
12

13
    let start = pre.next!;   // 第 m 个节点（反转区间的原头部）
14
    let then = start.next;   // 第 m+1 个节点（待头插的节点）
15

16
    // 执行 (n - m) 次头插
17
    for (let i = 0; i < n - m; i++) {
18
        start.next = then.next;   // 从原区间摘除 then
19
        then.next = pre.next;     // then 插入 pre 之后（成为新头部）
20
        pre.next = then;          // 更新 pre 的 next
21
        then = start.next;        // 更新 then 为下一个待移动节点
22
    }
23

24
    return dummy.next;
25
}

音乐

音乐