链表
1 什么是链表？
链表是一种在存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现。
最简单的链表就是单链表，如下图所示： 
其余的类型还有双向链表、循环链表等等，不同点就在于指针的运用。
2 LeetCode上的链表题
2.1 反转链表 (206 反转链表)
给你单链表的头节点 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。
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
（Yes, I can）
我的解法：
1 | # |
——————
2.2 反转链表 II (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
进阶： 你可以使用一趟扫描完成反转吗？
（Yes, I can）
我的解法：
1 | # |
——————
2.3 求两个链表的交点(160. 相交链表)
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表： 
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
注意：
- 如果两个链表没有交点，返回 null.
- 在返回结果后，两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
我的解法：
解法满足 O(n) 时间复杂度，且仅用 O(1) 内存。
1 | # |
—————
2.4 求链表是否存在环(141. 环形链表)
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
Yes, I can.
我的解法： 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#
# @lc app=leetcode.cn id=141 lang=python3
#
# [141] 环形链表
#
# @lc code=start
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if head == None:
return False
slow = head ## 慢指针
fast = head.next ## 快指针
meet = None
slow_step = 1 ## 相遇时slow指针走过的节点数
while fast != None:
fast = fast.next
if fast != None:
fast = fast.next
else:
return False
if slow == fast: ## 找到两者相遇
meet = slow
break
slow = slow.next
slow_step += 1
if meet == None:
return False
else:
return True
题目为Leetcode 142. 环形链表 II
我的解法： 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#
# @lc app=leetcode.cn id=142 lang=python3
#
# [142] 环形链表 II
#
# @lc code=start
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
"""
思路：
1. 快慢指针(快指针一次走两步，慢指针一次走一步)相遇时，记录该相遇节点；
2. 从头head处出发另一个慢指针和当前在meet节点的慢指针同时出发，直到两者相遇，便是入口节点。
解释：假设入口前的一段长为a，慢指针从环入口到与快指针相遇位置为b，环长度为c；
那么，快慢指针相遇时：快指针走的路程(a+b+c) = 慢指针走的路程的两倍(2*(a+b))；
由上式得出：a + b = c。所以，从相遇位置到环入口与a(入口前的一段)距离相等，
所以慢指针和从头开始的指针这时同时出发的相遇节点就是入口。
"""
fast = head
slow = head
meet = None
while fast != None:
slow = slow.next
fast = fast.next
if fast == None:
return None
fast = fast.next
if fast == slow:
meet = slow
break
if meet == None:
return None
while meet != None and head != None:
if meet == head:
return meet
head = head.next
meet = meet.next
return None
2.5 复制带随机指针的链表(138. 复制带随机指针的链表)
给你一个长度为 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 作为传入参数。
示例：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
提示：
- 0 <= n <= 1000
- -10000 <= Node.val <= 10000
- Node.random 为空（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#
# @lc app=leetcode.cn id=138 lang=python3
#
# [138] 复制带随机指针的链表
#
# @lc code=start
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
## 判断空
if head == None:
return None
node2id_dict = dict() ## 用于存储原链表节点与位置的映射
random_list = list() ## 存储链表节点的随机指针指向节点的位置
## 生成原链表节点与位置的映射
node = head
new_head = None
pre = None
i = 1
while node != None:
node2id_dict[node] = i
node = node.next
i += 1
node2id_dict[None] = 1002 ## 空节点映射的位置是一个相对无穷大的数
## 生成新的链表，同时存储链表节点的随机指针指向节点的位置
node = head
while node != None:
if new_head == None:
new_head = Node(node.val)
pre = new_head
else:
pre.next = Node(node.val)
pre = pre.next
random_list.append(node2id_dict[node.random])
node = node.next
new_id2node_dict = dict() ## 新链表的位置与节点的映射关系
## 生成新链表的位置与节点的映射关系
new_node = new_head
i = 1
while new_node != None:
new_id2node_dict[i] = new_node
new_node = new_node.next
i += 1
new_id2node_dict[1002] = None
## 连接新链表的random指针
new_node = new_head
while new_node != None:
new_node.random = new_id2node_dict[random_list.pop(0)]
new_node = new_node.next
return new_head
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
- 两个链表的节点数目范围是 [0, 50]
- -100 <= Node.val <= 100
- l1 和 l2 均按 非递减顺序 排列
我的解法： 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#
# @lc app=leetcode.cn id=21 lang=python3
#
# [21] 合并两个有序链表
#
# @lc code=start
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
from typing import List
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
"""
思路：对比两个链表上的两个指针对应的值，根据大小进行移动。见代码。
"""
if l1 == None:
return l2
if l2 == None:
return l1
pre1 = ListNode()
newhead = ListNode()
pre1.next = l1
node1 = l1
node2 = l2
while node1 != None and node2 != None:
if node1.val > node2.val:
tmp2 = node2.next
node2.next = node1
pre1.next = node2
pre1 = pre1.next
node2 = tmp2
if node1 == l1:
l1 = pre1
else:
node1 = node1.next
pre1 = pre1.next
if node2 != None:
pre1.next = node2
return l1
2.7 多个排序链表的合并(Leetcode 23. 合并K个升序链表)
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：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
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
- 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
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#
# @lc app=leetcode.cn id=23 lang=python3
#
# [23] 合并K个升序链表
#
# @lc code=start
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
"""
思路：
遍历所有的链表，将遍历到的数值作为字典的键、次数作为字典值进行保存；
然后sorted字典(对字典的键排序)后进行新链表的重建
"""
total_dict = defaultdict(int) ## 存储：数字-次数 键值对
if len(lists) == 0:
return None
for node in lists:
while node != None:
# 添加该链表的数字到字典中
total_dict[node.val] += 1
node = node.next
if len(total_dict) == 0:
return None
## 根据遍历到的数字和其次数进行链表重建
new_head = None
node = None
for key, val in sorted(total_dict.items()):
for _ in range(val):
if new_head == None:
new_head = ListNode(key)
node = new_head
else:
tmp = ListNode(key)
node.next = tmp
node = tmp
return new_head
1 | class Solution: |