本文解决的问题: 按主题归纳 链表 相关高频题型与通用解法。

适用范围: LeetCode 中文站题目,示例主要使用 Java。

阅读建议: 先识别数据结构与不变量,再结合题目约束选择算法,不要只记忆代码。

链表

相交链表

【】,【】

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

图示两个链表在节点 c1 开始相交**:**

1. 相交链表示例

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构 。

自定义评测:

评测系统 的输入如下(你设计的程序 不适用 此输入):

  • intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
  • skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。

**进阶:**你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案?

提示:
listA 中节点数目为 m

listB 中节点数目为 n

1 <= m, n <= 3 * 104

1 <= Node.val <= 105

0 <= skipA <= m

0 <= skipB <= n

如果 listA 和 listB 没有交点,intersectVal 为 0

如果 listA 和 listB 有交点,intersectVal == listA[skipA] == listB[skipB]

示例:
1. 相交链表示例

1
2
3
4
5
6
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
— 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。

1. 相交链表示例

1
2
3
4
5
输入:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Intersected at '2'
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [1,9,1,2,4],链表 B 为 [3,2,4]。
在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

1. 相交链表示例

1
2
3
4
5
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:No intersection
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。

代码:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/**
* 获取两个链表的交点节点
* 如果两个链表有交点,则从交点开始,两个链表的节点是一样的
* 解决这个问题的关键在于,通过某种方式让两个链表的长度相等,然后同步遍历两个链表,找到第一个相同的节点
* 本方法的巧妙之处在于,不需要真的去计算两个链表的长度差,而是通过交换遍历的方式,自然地抵消了长度差
*
* @param headA 第一个链表的头节点
* @param headB 第二个链表的头节点
* @return 返回两个链表的交点节点,如果没有交点,则返回null
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 如果任一链表为空,则不可能有交点,直接返回null
if (headA == null || headB == null) {
return null;
}

// 初始化两个指针,分别指向两个链表的头节点
ListNode a = headA, b = headB;

// 遍历两个链表,当任一指针不为空时继续循环
while (a != null || b != null) {
// 如果两个指针指向相同的节点,说明找到了交点,返回该节点
if (a == b) {
return a;
}

// 移动指针,如果指针a到达链表A的末尾,则将其指向链表B的头节点;否则继续向下移动
a = a == null ? headB : a.next;

// 移动指针,如果指针b到达链表B的末尾,则将其指向链表A的头节点;否则继续向下移动
b = b == null ? headA : b.next;
}

// 如果两个链表没有交点,则返回null
return null;
}

/**
* 获取两个链表的交点节点
*
* @param headA 第一个链表的头节点
* @param headB 第二个链表的头节点
* @return 返回交点节点,如果没有交点则返回null
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 初始化两个指针aList和bList分别指向两个链表的头节点
ListNode aList = headA;
ListNode bList = headB;

// 第一次遍历两个链表,分别移动指针直到其中一个链表结束
while (aList != null && bList != null) {
aList = aList.next;
bList = bList.next;
}

// 如果aList链表更长,将headA移动到与headB相同长度的位置
while (aList != null) {
headA = headA.next;
aList = aList.next;
}

// 如果bList链表更长,将headB移动到与headA相同长度的位置
while (bList != null) {
headB = headB.next;
bList = bList.next;
}

// 同时遍历两个链表,直到找到相同的节点(即交点)
while (headA != headB) {
headA = headA.next;
headB = headB.next;
}

// 返回交点节点,如果没有交点则返回null
return headA;
}

反转链表

【递归】、【链表】

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

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

提示:
链表中节点的数目范围是 [0, 5000]

5000 <= Node.val <= 5000

示例:
2. 反转链表示例

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

2. 反转链表示例

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

代码:

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
/**
* 反转一个单链表, 迭代方式
* 此方法通过迭代方式反转链表,不需要额外的存储空间,直接在原链表上进行操作
*
* @param head 链表的头节点如果链表为空或只有一个节点,则直接返回该节点
* @return 反转后的链表的头节点
*/
public ListNode reverseList(ListNode head) {
// 检查链表是否为空或只有一个节点,如果是,直接返回
if (head == null || head.next == null) {
return head;
}

// 初始化前一个节点pre,这里创建了一个新节点,其值与头节点相同
// 这个操作实际上是多余的,可以在进入循环后直接操作,这里可能是为了简化逻辑
ListNode pre = new ListNode(head.val);

// 遍历链表,直到最后一个节点
while (head.next != null) {
// 创建当前节点current,复制下一个节点的值
// 这种创建方式保证了不会改变原链表的结构
ListNode current = new ListNode(head.next.val);
// 移动head指针到下一个节点,为下一次迭代做准备
head = head.next;
// 将当前节点指向前面的节点,实现反转
current.next = pre;
// 更新pre指针,指向当前节点,为下一次迭代做准备
pre = current;
}

// 返回反转后的链表的头节点
return pre;
}

回文链表

【栈】、【递归】、【链表】、【双指针】

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

提示:
链表中节点数目在范围[1, 105] 内

0 <= Node.val <= 9

示例:
3. 回文链表示例

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

3. 回文链表示例

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

代码:

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
45
46
47
48
49
50
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode cur = head;
ListNode pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}

/**
* 判断一个链表是否为回文链表
*
* @param head 链表的头节点
* @return 如果链表是回文的,返回true;否则返回false
*/
public boolean isPalindrome(ListNode head) {
// 如果链表为空或只有一个节点,它是回文链表
if (head == null || head.next == null) {
return true;
}

// 使用快慢指针找到链表的中点
ListNode fast = head;
ListNode slow = head;
// 当快指针到达链表末尾时,慢指针正好在链表中点
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}

// 反转链表的后半部分
ListNode listNode = reverseList(slow.next);
// 比较前半部分和反转后的后半部分是否相同
while (listNode != null) {
if (listNode.val != head.val) {
return false;
}
listNode = listNode.next;
head = head.next;
}

// 如果所有节点匹配成功,则链表是回文的
return true;
}

两数相加

【递归】、【链表】、【数学】

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

提示:
每个链表中的节点数在范围 [1, 100] 内

0 <= Node.val <= 9

题目数据保证列表表示的数字不含前导零

示例:
4. 两数相加示例

1
2
3
输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807
1
2
输入:l1 = [0], l2 = [0]
输出:[0]
1
2
输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode();
ListNode current = dummyHead;
int carry = 0;

while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
carry = sum / 10;
current.next = new ListNode(sum % 10);
current = current.next;
}

return dummyHead.next;
}

环形链表

【哈希表】、【链表】、【双指针】

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

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

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

**进阶:**你能用 O(1)(即,常量)内存解决此问题吗?

提示:
链表中节点的数目范围是 [0, 104]

105 <= Node.val <= 105

pos 为 1 或者链表中的一个 有效索引 。

示例:
5. 环形链表示例

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

5. 环形链表示例

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

5. 环形链表示例

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode fast = head.next;
ListNode slow = head;
while(fast != slow) {
if (fast == null || fast.next == null) {
return false;
}
fast = fast.next.next;
slow = slow.next;
}
return true;
}

环形链表Ⅱ

【哈希表】、【链表】、【双指针】

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

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

不允许修改 链表。

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

提示:
链表中节点的数目范围在范围 [0, 104] 内

105 <= Node.val <= 105

pos 的值为 1 或者链表中的一个有效索引

示例:
6. 环形链表Ⅱ示例

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

6. 环形链表Ⅱ示例

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

6. 环形链表Ⅱ示例

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null&& slow.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
ListNode pre = head;
while(pre != slow) {
pre = pre.next;
slow = slow.next;
}
return pre;
}
}
return null;
}

K 个一组翻转链表

【递归】、【链表】

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

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

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

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

提示:
链表中的节点数目为 n

1 <= k <= n <= 5000

0 <= Node.val <= 1000

示例:
7. K 个一组翻转链表示例

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

7. K 个一组翻转链表示例

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

代码:

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
45
46
47
48
49
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k <= 1) {
return head;
}

// 创建一个虚拟头节点,方便处理链表头部的反转
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prevGroupEnd = dummy;

while (true) {
// 检查是否有足够的节点进行反转
ListNode kthNode = getKthNode(prevGroupEnd, k);
if (kthNode == null) {
break; // 不足 k 个节点,停止反转
}

ListNode nextGroupStart = kthNode.next;
ListNode[] reversedGroup = reverseList(prevGroupEnd.next, k);
prevGroupEnd.next = reversedGroup[0]; // 连接反转后的子链表
prevGroupEnd = reversedGroup[1]; // 更新 prevGroupEnd 到当前反转组的末尾

prevGroupEnd.next = nextGroupStart; // 连接下一组
}

return dummy.next;
}

// 获取从 start 节点开始的第 k 个节点
private ListNode getKthNode(ListNode start, int k) {
while (start != null && --k >= 0) {
start = start.next;
}
return start;
}

// 反转从 head 开始的 k 个节点,并返回反转后的头和尾
private ListNode[] reverseList(ListNode head, int k) {
ListNode prev = null;
ListNode cur = head;
ListNode next = null;
for (int i = 0; i < k; i++) {
next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return new ListNode[] {prev, head}; // 返回反转后的头和尾
}

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

【链表】、【双指针】

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

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

提示:
链表中结点的数目为 sz

1 <= sz <= 30

0 <= Node.val <= 100

1 <= n <= sz

示例:
8. 删除链表的倒数第 N 个结点示例

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
int length = getLength(head);
ListNode cur = dummy;
for (int i = 1; i < length - n + 1; ++i) {
cur = cur.next;
}
cur.next = cur.next.next;
ListNode ans = dummy.next;
return ans;
}

public int getLength(ListNode head) {
int length = 0;
while (head != null) {
++length;
head = head.next;
}
return length;
}

两两交换链表中的节点

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

提示:
链表中节点的数目在范围 [0, 100] 内

0 <= Node.val <= 100

示例:
9. 两两交换链表中的节点示例

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dumpNode1 = new ListNode(0, head);
ListNode dumpNode = dumpNode1;
while (dumpNode.next != null && dumpNode.next.next != null) {
ListNode temp2 = dumpNode.next.next;
ListNode temp1 = dumpNode.next;
dumpNode.next = temp2;
temp1.next = temp2.next;
temp2.next = temp1;
dumpNode = temp1;
}
return dumpNode1.next;
}

合并 K 个升序链表

【链表】、【分治】、【堆】、【归并排序】

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

提示:
k == lists.length

0 <= k <= 10^4

0 <= lists[i].length <= 500

10^4 <= lists[i][j] <= 10^4

lists[i] 按 升序 排列

lists[i].length 的总和不超过 10^4

示例:

1
2
3
4
5
6
7
8
9
10
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
1
2
输入:lists = []
输出:[]
1
2
输入:lists = [[]]
输出:[]

代码:

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
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null; // 边界条件:如果链表数组为空,返回 null
}
return mergeKListsHelper(lists, 0, lists.length - 1); // 调用分治递归函数
}

private ListNode mergeKListsHelper(ListNode[] lists, int start, int end) {
if (start == end) {
return lists[start]; // 如果只剩下一个链表,直接返回
}
if (start > end) {
return null; // 无效区间,返回 null
}
int mid = start + (end - start) / 2; // 计算中间索引
ListNode left = mergeKListsHelper(lists, start, mid); // 递归合并左半部分
ListNode right = mergeKListsHelper(lists, mid + 1, end); // 递归合并右半部分
return mergeTwoLists(left, right); // 合并左右两部分
}

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0); // 创建虚拟头节点
ListNode current = dummy;

while (l1 != null && l2 != null) { // 遍历两个链表
if (l1.val < l2.val) {
current.next = l1; // 取较小的节点
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next; // 移动指针
}

if (l1 != null) {
current.next = l1; // 连接剩余的链表
} else {
current.next = l2;
}

return dummy.next; // 返回合并后的链表
}

合并两个有序链表

【链表】、【归并排序】

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

提示:
两个链表的节点数目范围是 [0, 50]

100 <= Node.val <= 100

l1 和 l2 均按 非递减顺序 排列

示例:

1
2
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

代码:

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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}

随机链表的复制

【哈希表】、【链表】

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

提示:
0 <= n <= 1000

104 <= Node.val <= 104

Node.random 为 null 或指向链表中的节点。

示例:
12. 随机链表的复制示例

1
2
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

12. 随机链表的复制示例

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

12. 随机链表的复制示例

1
2
输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]

代码:

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
45
46
/**
* 复制带有随机指针的链表
* <p>
* 本方法通过三步完成复制: 1. 在原链表中每个节点后复制一个新节点 2. 设置新节点的随机指针 3. 将原链表和复制的新链表分离
*
* @param head 原链表的头节点
* @return 复制后的新链表的头节点
*/
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}

// 第一步:复制每个节点,并插入到原节点后面
Node current = head;
while (current != null) {
Node newNode = new Node(current.val);
newNode.next = current.next;
current.next = newNode;
current = newNode.next;
}

// 第二步:设置随机指针
current = head;
while (current != null) {
if (current.random != null) {
current.next.random = current.random.next;
}
current = current.next.next;
}

// 第三步:分离两个链表
current = head;
Node newHead = head.next;
Node newCurrent = newHead;
while (newCurrent.next != null) {
current.next = current.next.next;
newCurrent.next = newCurrent.next.next;
current = current.next;
newCurrent = newCurrent.next;
}
current.next = null;

return newHead;
}

排序链表

【链表】、【双指针】、【分治】、【排序】、【归并排序】

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。

**进阶:**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

提示:
链表中节点的数目在范围 [0, 5 * 104] 内

105 <= Node.val <= 105

示例:
13. 排序链表示例

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

代码:

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
45
46
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}

// 找到链表的中间节点
ListNode mid = findMiddle(head);
ListNode rightHead = mid.next;
mid.next = null;

// 递归地对左右两部分进行排序
ListNode left = sortList(head);
ListNode right = sortList(rightHead);

// 合并两个有序链表
return merge(left, right);
}

private ListNode findMiddle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
if (fast == null || fast.next == null) {
break;
}
slow = slow.next;
}
return slow;
}

private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 != null ? l1 : l2;
return dummy.next;
}

LRU缓存

请你设计并实现一个满足 LRU(最近最少使用)缓存约束的数据结构。

实现 LRUCache 类:

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 1 。
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

提示:
1 <= capacity <= 3000

0 <= key <= 10000

0 <= value <= 105

最多调用 2 * 105 次 get 和 put

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

代码:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
public class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {}
public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
}

private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
private int size;
private int capacity;
private DLinkedNode head, tail;

public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用伪头部和伪尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}

public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 如果 key 存在,先通过哈希表定位,再移到头部
moveToHead(node);
return node.value;
}

public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
// 如果 key 不存在,创建一个新的节点
DLinkedNode newNode = new DLinkedNode(key, value);
// 添加进哈希表
cache.put(key, newNode);
// 添加至双向链表的头部
addToHead(newNode);
++size;
if (size > capacity) {
// 如果超出容量,删除双向链表的尾部节点
DLinkedNode tail = removeTail();
// 删除哈希表中对应的项
cache.remove(tail.key);
--size;
}
}
else {
// 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部
node.value = value;
moveToHead(node);
}
}

private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}

private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}

private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}

private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}

参考资料