反转链表
206. 反转链表
给你单链表的头节点head，请你反转链表，并返回反转后的链表。
示例 1：
1
2
| 输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
|
示例 2：
1
2
| 输入：head = [1,2]
输出：[2,1]
|
示例 3：
提示：
- 链表中节点的数目范围是
[0, 5000]
5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
|
92. 反转链表 II
给你单链表的头指针head和两个整数left和right，其中left <= right。请你反转从位置left到位置right的链表节点，返回反转后的链表。
示例 1：
1
2
3
| 输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
|
示例 2：
1
2
3
| 输入：head = [5], left = 1, right = 1
输出：[5]
|
提示：
- 链表中节点数目为
n
1 <= n <= 500500 <= Node.val <= 5001 <= left <= right <= n
进阶： 你可以使用一趟扫描完成反转吗？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(), p0 = dummy;
dummy.next = head;
for (int i = 0; i < left - 1; ++i) {
p0 = p0.next;
}
ListNode pre = p0, cur = p0.next;
for (int i = 0; i < right - left + 1; ++i) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
p0.next.next = cur;
p0.next = pre;
return dummy.next;
}
}
|
25. K 个一组翻转链表
给你链表的头节点 head ，每 k **个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k **的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
1
2
3
| 输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
|
示例 2：
1
2
3
| 输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
|
提示：
- 链表中的节点数目为
n
1 <= k <= n <= 50000 <= Node.val <= 1000
进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(), p0 = dummy;
dummy.next = head;
int n = 0;
for (; head != null; head = head.next) {
++n;
}
ListNode pre = null, cur = p0.next;
for (; n >= k; n -= k) {
for (int i = 0; i < k; ++i) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
ListNode next = p0.next;
p0.next = pre;
p0 = next;
p0.next = cur;
}
return dummy.next;
}
}
|
24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
1
2
3
| 输入：head = [1,2,3,4]
输出：[2,1,4,3]
|
示例 2：
示例 3：
提示：
- 链表中节点的数目在范围
[0, 100] 内
0 <= Node.val <= 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, head), p0 = dummy, pre = null, cur = p0.next;
while (p0.next != null && p0.next.next != null) {
for (int i = 0; i < 2; ++i) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
ListNode next = p0.next;
p0.next = pre;
p0 = next;
p0.next = cur;
}
return dummy.next;
}
}
|
快慢指针 环形链表 重排链表
876. 链表的中间结点
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
1
2
3
4
| 输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。
|
示例 2：
1
2
3
4
| 输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
|
提示：
- 链表的结点数范围是
[1, 100]
1 <= Node.val <= 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
for (ListNode fast = head; fast != null && fast.next != null; slow = slow.next, fast = fast.next.next);
return slow;
}
}
|
141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
1
2
3
4
| 输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
|
示例 2：
1
2
3
4
| 输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
|
示例 3：
1
2
3
4
| 输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
|
提示：
- 链表中节点的数目范围是
[0, 104]
105 <= Node.val <= 105pos 为 1 或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
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 (fast == slow) {
return true;
}
}
return false;
}
}
|
142. 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
1
2
3
4
| 输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
|
示例 2：
1
2
3
4
| 输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
|
示例 3：
1
2
3
4
| 输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
|
提示：
- 链表中节点的数目范围在范围
[0, 104] 内
105 <= Node.val <= 105pos 的值为 1 或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) {
while (head != slow) {
head = head.next;
slow = slow.next;
}
return head;
}
}
return null;
}
}
|
143. 重排链表
给定一个单链表 L **的头节点 head ，单链表 L 表示为：
1
| L0 → L1 → … → Ln - 1 → Ln
|
请将其重新排列后变为：
1
| L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
|
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
1
2
| 输入：head = [1,2,3,4]
输出：[1,4,2,3]
|
示例 2：
1
2
| 输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]
|
提示：
- 链表的长度范围为
[1, 5 * 104]
1 <= node.val <= 1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
class Solution {
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;
}
private ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
public void reorderList(ListNode head) {
ListNode mid = middleNode(head), head2 = reverseList(mid);
while (head2.next != null) {
ListNode next1 = head.next, next2 = head2.next;
head.next = head2;
head = next1;
head2.next = head;
head2 = next2;
}
}
}
|
234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
1
2
3
| 输入：head = [1,2,2,1]
输出：true
|
示例 2：
1
2
3
| 输入：head = [1,2]
输出：false
|
提示：
- 链表中节点数目在范围
[1, 105] 内
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
class Solution {
ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
public boolean isPalindrome(ListNode head) {
ListNode mid = middleNode(head), head2 = reverseList(mid);
while (head != null && head2 != null) {
if (head.val != head2.val) {
return false;
}
head = head.next;
head2 = head2.next;
}
return true;
}
}
|
前后指针 删除 去重
237. 删除链表中的节点
有一个单链表的 head，我们想删除它其中的一个节点 node。
给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。
链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。
删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：
- 给定节点的值不应该存在于链表中。
- 链表中的节点数应该减少 1。
node 前面的所有值顺序相同。node 后面的所有值顺序相同。
自定义测试：
- 对于输入，你应该提供整个链表
head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。
- 我们将构建链表，并将节点传递给你的函数。
- 输出将是调用你函数后的整个链表。
示例 1：
1
2
3
4
| 输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9
|
示例 2：
1
2
3
| 输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9
|
提示：
- 链表中节点的数目范围是
[2, 1000]
1000 <= Node.val <= 1000- 链表中每个节点的值都是 唯一 的
- 需要删除的节点
node 是 链表中的节点 ，且 不是末尾节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
|
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n **个结点，并且返回链表的头结点。
示例 1：
1
2
3
| 输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
|
示例 2：
1
2
3
| 输入：head = [1], n = 1
输出：[]
|
示例 3：
1
2
3
| 输入：head = [1,2], n = 1
输出：[1]
|
提示：
- 链表中结点的数目为
sz
1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head), left = dummy, right = dummy;
for (int i = 0; i < n; ++i) {
right = right.next;
}
while (right.next != null) {
left = left.next;
right =right.next;
}
left.next = left.next.next;
return dummy.next;
}
}
|
83. 删除排序链表中的重复元素
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
1
2
3
| 输入：head = [1,1,2]
输出：[1,2]
|
示例 2：
1
2
3
| 输入：head = [1,1,2,3,3]
输出：[1,2,3]
|
提示：
- 链表中节点数目在范围
[0, 300] 内
100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return null;
}
ListNode cur = head;
while (cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
}
|
82. 删除排序链表中的重复元素 II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
1
2
3
| 输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
|
示例 2：
1
2
3
| 输入：head = [1,1,1,2,3]
输出：[2,3]
|
提示：
- 链表中节点数目在范围
[0, 300] 内
100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0, head), 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;
}
}
|
203. 移除链表元素
给你一个链表的头节点head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回新的头节点。
示例 1：
1
2
| 输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
|
示例 2：
1
2
| 输入：head = [], val = 1
输出：[
|
示例 3：
1
2
| 输入：head = [7,7,7,7], val = 7
输出：[]
|
提示：
- 列表中的节点数目在范围
[0, 104] 内
1 <= Node.val <= 500 <= val <= 50
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0, head), cur = dummy;
while (cur.next != null) {
if (cur.next.val == val) {
while (cur.next != null && cur.next.val == val) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummy.next;
}
}
|
