链表：反转链表、快慢指针、删除链表【零神基础精讲】

来源0x3f：https://space.bilibili.com/206214

反转链表

206. 反转链表

难度简单2859

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

图片来自：https://leetcode.cn/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-shuang-zhi-zhen-di-gui-yao-mo-/

递归

class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null) return head;//确保有头结点ListNode cur = reverseList(head.next);// 翻转头节点 第二个节点的指向head.next.next = head;// 此时的 head 节点为尾节点，next 需要指向 NULLhead.next = null;return cur;}
}

迭代

class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null; // 前指针结点ListNode cur = head; // 当前指针结点while(cur != null){ListNode tmp = cur.next; //临时结点保存遍历顺序cur.next = pre; //将当前节点指向它前面的节点pre = cur; //前指针后移cur = tmp; //当前指针后移}return pre;}
}

头插法

class Solution {public ListNode reverseList(ListNode head) {ListNode p = head;ListNode res = new ListNode(-1, null);while(p != null){ListNode tmp = p.next;p.next = res.next;res.next = p;p = tmp;}return res.next;}
}

---

92. 反转链表 II

难度中等1446

给你单链表的头指针 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

进阶： 你可以使用一趟扫描完成反转吗？

性质：反转结束后，从原来的链表上看：

• pre指向反转这一段的末尾
• cur指向反转这一段后续的下一个结点

class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummy = new ListNode(-1);// 初始化哨兵结点，使得处理第一个结点与第i个结点相同dummy.next= head;ListNode p0 = dummy;// 找到要反转的链表左侧的上一个结点for(int i = 0; i < left-1; i++){p0 = p0.next;} ListNode pre = null;ListNode cur = p0.next;for(int i = 0; i < right-left+1; i++){ListNode nxt = cur.next;cur.next = pre;pre = cur;cur = nxt;}p0.next.next = cur;p0.next = pre;return dummy.next;}   
}

---

25. K 个一组翻转链表

难度困难1857

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

**进阶：**你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

class Solution {public ListNode reverseKGroup(ListNode head, int k) {//统计一下链表长度int n = 0;ListNode cnt = head;while(cnt != null){n++;cnt = cnt.next;}ListNode dummy = new ListNode(-1);// 初始化哨兵结点，使得处理第一个结点与第i个结点相同dummy.next= head;ListNode p0 = dummy;while(n >= k){ // 循环n/k次n -= k;ListNode pre = null;ListNode cur = p0.next;for(int i = 0; i < k; i++){ListNode nxt = cur.next;cur.next = pre;pre = cur;cur = nxt;}ListNode nxt = p0.next;p0.next.next = cur;p0.next = pre;p0 = nxt;}return dummy.next;}
}

剑指 Offer 06. 从尾到头打印链表

难度简单354

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

从尾到头打印的过程就是递归的过程

class Solution {List<Integer> tmp = new ArrayList<>();public int[] reversePrint(ListNode head) {recur(head);int[] res = new int[tmp.size()];for(int i = 0; i < res.length; i++){res[i] = tmp.get(i);}return res;}void recur(ListNode head){if(head == null) return;recur(head.next);tmp.add(head.val);}
}

---

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

难度中等1715

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

class Solution {public ListNode swapPairs(ListNode head) {ListNode sentinel = new ListNode(-1);sentinel.next = head;ListNode p = sentinel;while(p.next != null && p.next.next != null){ListNode nxt = p.next;p.next = nxt.next;nxt.next = p.next.next;p.next.next = nxt;p = p.next.next;}return sentinel.next;}
}

快慢指针（环形链表、重排链表）

876. 链表的中间结点

难度简单795

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

• 给定链表的结点数介于 1 和 100 之间。

class Solution {public ListNode middleNode(ListNode head) {ListNode fast = head, slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}return slow;}
}

---

141. 环形链表

难度简单1740

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

• 链表中节点的数目范围是 [0, 104]
• -105 <= Node.val <= 105
• pos 为 -1 或者链表中的一个 有效索引 。

public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head, slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow) return true;}return false;}
}

---

142. 环形链表 II

难度中等1945

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

**进阶：**你是否可以使用 O(1) 空间解决此题？

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head, slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow) break;}if(fast == null || fast.next == null) return null;ListNode p = head;while(p != fast){p = p.next;fast = fast.next;}return p;}
}

---

※143. 重排链表

难度中等1136

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

提示：

• 链表的长度范围为 [1, 5 * 104]
• 1 <= node.val <= 1000

class Solution {public void reorderList(ListNode head) {ListNode mid = middleNode(head);ListNode head2 = reverseList(mid);while (head2.next != null) {ListNode nxt = head.next;ListNode nxt2 = head2.next;head.next = head2;head2.next = nxt;head = nxt;head2 = nxt2;}}// 876. 链表的中间结点private ListNode middleNode(ListNode head) {ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}// 206. 反转链表private ListNode reverseList(ListNode head) {ListNode pre = null, cur = head;while (cur != null) {ListNode nxt = cur.next;cur.next = pre;pre = cur;cur = nxt;}return pre;}
}

---

234. 回文链表

难度简单1614

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

**进阶：**你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

class Solution {public boolean isPalindrome(ListNode head) {ListNode mid = middleNode(head);ListNode rev = reverseList(mid);ListNode p = head;while(p != null && rev != null){if(p.val != rev.val) return false;p = p.next;rev = rev.next;}return true;}// 876. 链表的中间结点private ListNode middleNode(ListNode head) {ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}// 206. 反转链表private ListNode reverseList(ListNode head) {ListNode pre = null, cur = head;while (cur != null) {ListNode nxt = cur.next;cur.next = pre;pre = cur;cur = nxt;}return pre;}
}

删除链表节点

237. 删除链表中的节点

难度中等1234

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

• 给定节点的值不应该存在于链表中。
• 链表中的节点数应该减少 1。
• node 前面的所有值顺序相同。
• node 后面的所有值顺序相同。

自定义测试：

• 对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。
• 我们将构建链表，并将节点传递给你的函数。
• 输出将是调用你函数后的整个链表。

示例 1：

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

示例 2：

输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9

提示：

• 链表中节点的数目范围是 [2, 1000]
• -1000 <= Node.val <= 1000
• 链表中每个节点的值都是 唯一 的
• 需要删除的节点 node 是 链表中的节点 ，且 不是末尾节点

class Solution {public void deleteNode(ListNode node) {node.val = node.next.val;node.next = node.next.next;}
}

---

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

难度中等2407

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

**进阶：**你能尝试使用一趟扫描实现吗？

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode sentinel = new ListNode(-1);sentinel.next = head;ListNode end = sentinel;int i = 0;while(end.next != null && i < n){end = end.next;i++;}ListNode p = sentinel;while(end.next != null){p = p.next;end = end.next;}p.next = p.next.next;return sentinel.next;}
}

---

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

难度简单940

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

class Solution {public ListNode deleteDuplicates(ListNode head) {Set<Integer> set = new HashSet<>();ListNode sentinel = new ListNode(-1, head);ListNode p = sentinel;while(p.next != null){if(set.contains(p.next.val)){p.next = p.next.next;}else{set.add(p.next.val);p = p.next;}}return sentinel.next;}
}

---

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

难度中等1061

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode dummy = new ListNode(-1, head);ListNode cur = dummy;while(cur.next != null && cur.next.next != null){int val = cur.next.val;if(cur.next.next.val == val){while(cur.next != null && cur.next.val == val){cur.next = cur.next.next;}}else{cur = cur.next;}}return dummy.next;}
}

偷懒写法

class Solution {public ListNode deleteDuplicates(ListNode head) {Map<Integer, Integer> map = new HashMap<>();ListNode sentinel = new ListNode(-1, head);ListNode p = sentinel;while(p.next != null){map.put(p.next.val, map.getOrDefault(p.next.val, 0)+1);p = p.next;}ListNode newsentinel = new ListNode(-1);ListNode cur = newsentinel;p = sentinel;while(p.next != null){if(map.get(p.next.val) == 1){ListNode tmp = new ListNode(p.next.val);cur.next = tmp;cur = tmp;}p = p.next;}cur.next = null;return newsentinel.next;}
}

                cur.next = cur.next.next;}}else{cur = cur.next;}}return dummy.next;
}

}

偷懒写法```java
class Solution {public ListNode deleteDuplicates(ListNode head) {Map<Integer, Integer> map = new HashMap<>();ListNode sentinel = new ListNode(-1, head);ListNode p = sentinel;while(p.next != null){map.put(p.next.val, map.getOrDefault(p.next.val, 0)+1);p = p.next;}ListNode newsentinel = new ListNode(-1);ListNode cur = newsentinel;p = sentinel;while(p.next != null){if(map.get(p.next.val) == 1){ListNode tmp = new ListNode(p.next.val);cur.next = tmp;cur = tmp;}p = p.next;}cur.next = null;return newsentinel.next;}
}