Lyncien's blog

LeetCode刷题笔记——链表

2022-01-17

总结

链表相关的题目整体上难度不大

主要是对指针的指向修改容易出错

赋值顺序错误导致丢失了某个节点之后的所有结点
访问了空指针
计数次数与预期相差1

链表的特性

无法随机访问，只能从头开始单向前进
初始时链表的长度未知
（单链表）从某个节点无法获取其前一个节点

双指针

使用多个指针同时前进，实现到达链表中的某个偏移位置

快慢指针：以不同的速度前进，快指针每次前进两个结点，慢指针每次前进一个结点，快指针到末尾时慢指针到达链表中点
以一定的间隔同时前进，A指针先前进k步，之后AB指针同时前进，A指针到末尾时，B指针在倒数第k个节点

prev指针

对与需要删除或移动某个节点的情况，需要修改该节点前一个结点的next指针

如果循环时迭代的变量视为当前节点，则需要额外维护一个prev变量

当然，也可以直接将循环时迭代的变量视为前一个节点，使用该节点->next->val，这样可以省去prev变量

dummy结点

通常以一个不存储实际数值的哑结点作为头结点，以统一操作，避免在循环中进行额外的判断（是否为head）

如果使用上面的prev变量，初始时prev就指向dummy

注意点

对循环边界条件的判断

链表是否结束，注意判断是用p!=nullptr还是p->next!=nullptr
前进指定的次数

对于需要计数的情况

尽可能不要在循环的判断条件中对计数变量使用++和--后缀运算符，特别是与结点指针p != nullptr的判断进行逻辑与&&运算时
因为后缀运算的副作用是否执行与执行位置不明显，带来思维上的负担，容易出现边界情况计算错误
好的做法应该是在循环体中修改计数变量（同时修改结点指针）

对于指针指向的修改

需要额外的变量暂存某个指针
以一定的顺序赋值，避免错误覆盖而丢失指针
每次循环结束后某个指针变量的指向是明确的（“语义”不变的）

关于递归实现

递归虽然更简洁，但边界条件也容易出错，并且栈开销较大，尽量不使用

具体题目

简单题

2. 两数相加

以链表存储的两个数，低位在前

直接相加即可，注意最后的进位

445. 两数相加 II

以链表存储的两个数，高位在前

先入栈或先翻转链表

19. 删除链表的倒数第 N 个结点

经典双指针，注意删除的有可能是首结点，需要dummy

A从head先前进N，然后B从dummy出发与A一起前进，A==null时，B为倒数第N的前一个结点

21. 合并两个有序链表

简单归并，注意最后接上未遍历完的那个链表

83. 删除排序链表中的重复元素

题意：删除已排序链表中所有重复数字的节点，使每个元素只出现一次

对每个结点，不断删除相同值的下一个结点

82. 删除排序链表中的重复元素 II

题意：删除已排序链表中所有重复数字的节点，只留下原先只出现一次的数字

这题有可能删除头结点，需要dummy

设置prev和curr，对每个结点curr，不断删除相同值的下一个结点，最后删除curr

141. 环形链表

快慢指针判断环，注意循环的边界条件

如果fast遇到nullptr，说明没有环

203. 移除链表元素

判断下一个元素的值即可，若相等，删除下一个元素

206. 反转链表

经典方法，前中后三个指针遍历

ListNode* prev = nullptr;
ListNode* curr = head;
ListNode* next = nullptr;
while (curr) {
    next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
}
return prev;

还有一种奇技淫巧，

ListNode *p;
for (p = nullptr; head; )
    tie(p, head, head->next) = tuple<ListNode*, ListNode*, ListNode*>(head, head->next, p);
return p;

237. 删除链表中的节点

比较有意思的题目，由于不知道当前节点的前一个结点，无法直接删除，我们可以把下一个结点（必须存在）的值放到当前节点存储，然后删除下一个结点

725. 分隔链表

题意：把链表按顺序平均切成k份，任意两部分的长度差距不能超过 1，排在前面的部分的长度应该大于或等于排在后面的长度。

先计算长度n，求每份基本长度n/k，n%k余数r，前r段每段长度n/k+1，剩下的每段长度为n/k，对两种长度分别循环切分

876. 链表的中间结点

经典的快慢指针

1290. 二进制链表转整数

遍历，移位，累加

1669. 合并两个链表

题意：给你两个链表，它们包含的元素分别为 n 个和 m 个。请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。

注意前进次数，前进a-1次获得删除区间的前一个结点，再前进b+1次，获得删除区间的后一个结点

1721. 交换链表中的节点

题意：交换链表正数第 k 个节点和倒数第 k 个节点的值

双指针，A先前进k-1次，记录A的位置获得第k

A+1（注意这里），之后AB一起，A==null时，B就是倒数k

2058. 找出临界点之间的最小和最大距离

题意：找出链表的两个严格极(大或小)值之间的最大和最小距离

前中后三个指针，依次找到所有极值的位置，更新最小间距

2095. 删除链表的中间节点

快慢指针找中点的前一个结点，注意输入和循环的边界条件

或者多用一个pre存放上一次的慢指针，比较清晰不会混乱

中等题

24. 两两交换链表中的节点

递归方法：简单

迭代方法：

交换之前的节点关系是 temp -> node1 -> node2，交换之后的节点关系要变成 temp -> node2 -> node1，因此需要进行如下操作。

temp.next = node2
node1.next = node2.next
node2.next = node1

完成上述操作之后，节点关系即变成 temp -> node2 -> node1。再令 temp = node1，对链表中的其余节点进行两两交换，直到全部节点都被两两交换。

61. 旋转链表

题意：将链表每个节点向右移动 k_ _个位置

先求长度n，k=k%n，k==0时无需处理

思路：将链表连接成环，然后在指定位置断开

具体：尾部下一个节点连到头成环，然后找到新链表的最后一个节点（即原链表的第n - 1 - k个节点），将当前闭合为环的链表断开

86. 分隔链表

题意：给一个特定值x，调整链表使得所有小于 x 的节点都出现在 大于或等于 x 的节点之前，应当保留两个分区中每个节点的初始相对位置。

效果相当于快排里的划分函数。

但链表不能从后往前迭代。因此，开一个dummy存放遍历时遇到的所有>=x的结点，原head的链表保留<x的结点，最后链接两个链表

92. 反转链表 II

题意：反转链表中的一个区间[left,right]，下标从1开始

注意设置dummy，因为left可能是1，这样我们总是可以从dummy先前进left-1次获得left的前一个结点p，然后常规翻转right-left+1次

最后设置原p->next的next为翻转后剩下结点的首节点，p->next设为翻转后的首节点

142. 环形链表 II

题意：找出环形链表的入口点

快慢指针，直到快为null（说明无环，返回）或快==慢

此时slow走n步，fast走2n步，fast比slow多走一圈，则圈长为n

设不在圈中的部分长度为k，则slow在圈中已走n-k步，说明再走k步就会回到入口点（进圈的第一个结点）

让fast回head，与slow同速度前进，直到相等，则此时slow走n+k步，比fast多1圈，则fast走了k步，两者都在入口点

143. 重排链表

147. 对链表进行插入排序

设置一个指针p指向已排序的末尾节点，遍历链表，若当前节点大于末尾，则p++，否则取出当前节点从头开始寻找插入点

160. 相交链表

题意：两个链表可能在某个结点相交（之后的结点是一样的）。返回相交的其实结点，不存在返回Null

简单的方法：先算长度，然后重新遍历，让长的链表先走长度差，之后同时遍历两个链表，判断节点是否一样

巧妙的方法：同时遍历两个链表，各自到末尾时开始遍历另一个链表，直到二者相等（包括都为null的情况，说明不相交）

234. 回文链表

题意：判断链表的数字是否回文

方法一：快慢指针 + 反转链表，不额外使用存储的方法。先快慢指针找到中点，将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后将链表恢复原样。

方法二：快慢指针找中点，中点后的结点存入一个栈中

方法三：巧妙的递归方法，需要使用全局变量

ListNode* frontPointer;
bool recursivelyCheck(ListNode* currentNode) {
    if (currentNode != nullptr) {
        if (!recursivelyCheck(currentNode->next)) {
            return false;
        }
        if (currentNode->val != frontPointer->val) {
            return false;
        }
        frontPointer = frontPointer->next;
    }
    return true;
}
bool isPalindrome(ListNode* head) {
    frontPointer = head;
    return recursivelyCheck(head);
}

328. 奇偶链表

题意：奇数下标的结点连在一起，偶数下标的结点连在一起作为后半部分

开另一个dummy结点存储取出的偶结点，最后接到原链表后

817. 链表组件

题意：计算链表中元素连续出现在某个数组中的区间数量

先把数组元素存入集合，方便查找，然后遍历链表即可

2130. 链表最大孪生和

题意：在一个大小为 n 且 n 为偶数的链表中，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点，求最大的孪生结点元素和

类似回文链表

138. 复制带随机指针的链表

题意：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。返回这个链表的 __深拷贝__。复制链表中的指针都不应指向原链表中的节点。

简单方法：使用哈希表记录新旧结点关系，按序构建新链表，然后再次遍历，根据hash表重建random指针

巧妙方法：

首先将该链表中每一个节点拆分为两个相连的节点，例如对于链表 $A \rightarrow B \rightarrow C$ ，我们可以将其拆分为 $A \rightarrow A' \rightarrow B \rightarrow B' \rightarrow C \rightarrow C'$ 。对于任意一个原节点 $S$ ，其拷贝节点 $S'$ 即为其后继节点。

然后，重建random指针，对于一个原链表节点执行p->next->random = p->random->next

最后，将两个链表拆分开。

困难题

23. 合并K个升序链表

朴素方法：k-1次循环，每次取一个链表合并到第一个链表，O(nk^2)

进阶方法：分治合并，logk次，O(nklogk)

更好的方法：维护当前每个链表没有被合并的元素的最前面一个， $k$ 个链表就最多有 $k$ 个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，用优先队列来优化这个过程。优先队列中的元素不超过 $k$ 个，最多有 $kn$ 个点，插入删除各一次，故总的时间代价即渐进时间复杂度为 $O(kn \times \log k)$ 。