【面试高频题】热门数据结构面试题合集（链表）
本文正在参加「金石计划」
链表
链表一直是面试数据结构中的重中之重，今天通过 555 道与链表相关的题目来进行学习。
92. 反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
提示：
- 链表中节点数目为 n
- 1 <= n <= 500
- -500 <= Node.val <= 500
- 1 <= left <= right <= n
朴素解法
为了减少边界判断，我们可以建立一个虚拟头结点 dummy，使其指向 head，最终返回 dummy.next。
这种「哨兵」技巧能应用在所有的「链表」题目。
黄色部分的节点代表需要「翻转」的部分：
之后就是常规的模拟，步骤我写在示意图里啦 ~
代码：
class Solution {
public ListNode reverseBetween(ListNode head, int l, int r) {
ListNode dummy = new ListNode(0);
dummy.next = head;
r -= l;
ListNode hh = dummy;
while (l-- > 1) hh = hh.next;
ListNode a = hh.next, b = a.next;
while (r-- > 0) {
ListNode tmp = b.next;
b.next = a;
a = b;
b = tmp;
}
hh.next.next = b;
hh.next = a;
return dummy.next;
}
}
- 时间复杂度：O(n)O(n)O(n)
- 空间复杂度：O(1)O(1)O(1)
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
提示：
- 链表中结点的数目为
sz - 1<=sz<=301 <= sz <= 301<=sz<=30
- 0<=Node.val<=1000 <= Node.val <= 1000<=Node.val<=100
- 1<=n<=sz1 <= n <= sz1<=n<=sz
快慢指针
删除链表的倒数第 n 个结点，首先要确定倒数第 n 个节点的位置。
我们可以设定两个指针，分别为 slow 和 fast，刚开始都指向 head。
然后先让 fast 往前走 n 步，slow 指针不动，这时候两个指针的距离为 n。
再让 slow 和 fast 同时往前走（保持两者距离不变），直到 fast 指针到达结尾的位置。
这时候 slow 会停在待删除节点的前一个位置，让 slow.next = slow.next.next 即可。
但这里有一个需要注意的边界情况是：如果链表的长度是 L，而我们恰好要删除的是倒数第 L 个节点（删除头节点），这时候 fast 往前走 n 步之后会变为 null，此时我们只需要让 head = slow.next 即可删除。
代码：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head.next == null) return null;
ListNode slow = head, fast = head;
while (n-- > 0) fast = fast.next;
if (fast == null) {
head = slow.next;
} else {
while (fast.next != null) {
slow = slow.next; fast = fast.next;
}
slow.next = slow.next.next;
}
return head;
}
}
- 时间复杂度：需要扫描的长度为链表的长度。复杂度为 O(n)O(n)O(n)
- 空间复杂度：O(1)O(1)O(1)
141. 环形链表
给你一个链表的头节点 head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 000 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
提示：
- 链表中节点的数目范围是 [0,104][0, 10^4][0,104]
- −105<=Node.val<=105-10^5 <= Node.val <= 10^5−105<=Node.val<=105
pos为-1或者链表中的一个 有效索引 。
进阶：你能用 O(1)O(1)O(1)（即，常量）内存解决此问题吗？
快慢指针
这是一道「快慢指针」的模板题。
使用两变量 slow 和 fast 分别代表快慢指针，slow 每次往后走一步，而 fast 每次往后两步，两者初始化均为 head。
若链表无环，则 fast 必然会先走到结尾，算法正常结束；若链表有环，当 slow 来到环入口时，fast 必然已经在环中的某个位置，此时再继续进行，由于存在速度差，发生相遇必不可能是 slow 追上 fast，而只能是 fast 从后方追上 slow，由于速度差为 111，因此最多会消耗不超过环节点个数的回合，两者即会相遇。
代码：
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
}
- 时间复杂度：O(n)O(n)O(n)
- 空间复杂度：O(1)O(1)O(1)
142. 环形链表 II
给定一个链表的头节点 head，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
提示：
- 链表中节点的数目范围在范围 [0,104][0, 10^4][0,104] 内
- −105<=Node.val<=105-10^5 <= Node.val <= 10^5−105<=Node.val<=105
pos的值为-1或者链表中的一个有效索引
进阶：你是否可以使用 O(1)O(1)O(1) 空间解决此题？
快慢指针
起始使用 slow 和 fast 作为慢快指针（slow 每次走一步，fast 每次走两步），起始均为 head。
若 fast 顺利走到结尾，说明链表无环，直接返回 null；
若两者成功相遇，说明链表有环。我们定义链表起点到环入口距离为 x，环内节点数量为 y。那么从链表起点到环入口的任意路径都能归纳成 x+k×yx + k \times yx+k×y（其中 kkk 为大于等于 000 的任意值）。
当两者首次相遇时，假设 slow 走的距离为 d1，而 fast 走的距离为 d2，根据速度差定义可知 d2=d1×2d2 = d1 \times 2d2=d1×2。同时根据 141. 环形链表 结论，两者必然在环中相遇，且必然是 fast 在环内从后面追上 slow，因此 d2 相比于 d1 必然是多了 y 的整数倍，即有 d2=d1+m×yd2 = d1 + m \times yd2=d1+m×y（其中 mmm 为圈数），即可推导出 d1=m×yd1 = m \times yd1=m×y。
同时根据链表起点到环入口的任意路径均表示为 x+k×yx + k \times yx+k×y，我们知道如果 slow 再走 x 步会到达环入口，同时链表起点到环入口也是 x 步，因此我们可以复用 fast，将其复位到链表起点，和 slow 一起每次往前一步，当两者再次相遇，必然是同时位于环入口。
同时该做法容易拓展成求 x 和求 y 等问题。
代码：
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode base = head;
ListNode slow = head, fast = head;
boolean ok = false;
while (!ok && fast != null && fast.next != null) {
slow = slow.next; fast = fast.next.next;
if (slow == fast) ok = true;
}
if (!ok) return null;
fast = head;
while (slow != fast) {
slow = slow.next; fast = fast.next;
}
return slow;
}
}
- 时间复杂度：O(n)O(n)O(n)
- 空间复杂度：O(1)O(1)O(1)
总结
与数组相比，同为线性数据结构的链表具有 O(1)O(1)O(1) 插入、删除的特性，这对于一些删除后进行元素挪动，或新增后触发扩容的算法题而言，具有降低复杂度的意义。