链表

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）

我的解法：

python
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
#
# @lc app=leetcode.cn id=206 lang=python3
#
# [206] 反转链表
#

# @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 reverseList(self, head: ListNode) -> ListNode:
        ## 迭代 (头插法进行逆序)
        # if head == None:
        #     return head
        # pre_head = ListNode()
        # node = head
        # inverse_node = None
        # while node != None:
        #     tmp = node.next
        #     node.next = pre_head.next
        #     pre_head.next = node
        #     node = tmp
        # return pre_head.next
        
        ##递归
        def reverseLinkedList(pre, node):
        	## pre代表前一节点
        	## node代表当前节点
            if node == None:
                return pre
            tmp = node.next ## 提前将node的下一节点保存
            node.next = pre ## 将当前节点的指针指向前一节点
            return reverseLinkedList(node, tmp) 
        return reverseLinkedList(None, head)

——————

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）

我的解法：

python
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
#
# @lc app=leetcode.cn id=92 lang=python
#
# [92] 反转链表 II
#

# @lc code=start
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseBetween(self, head, left, right):
        """
        :type head: ListNode
        :type left: int
        :type right: int
        :rtype: ListNode
        """
        ## 思路：从头开始扫描并记录位置，当位置到达left时进行头插法，直到到达right位置。

        if left == right:
            return head
        
        pre = head ## pre记录left的前一个节点
        node = head ## node用于遍历
        position = 1 ## 记录位置
        ## 找到left位置的节点
        while position != left:
            pre = node
            node = node.next
            position += 1
        ## 特殊情况判断
        if position == 1:
            pre = ListNode(502)

        tail = node ## tail记录逆转的尾节点
        post = node ## post记录头插法位置的后一节点
        ## 找到开始头插法的节点
        node = node.next
        position += 1
        ## 循环进行头插法，直到到达right的节点
        while position <= right:
            pre.next = node
            node = node.next
            pre.next.next = post
            post = pre.next
            position += 1
        ## 逆转的尾节点连接到后面的节点
        tail.next = node
        
        ## 特殊情况判断
        if pre.val == 502:
            head = pre.next
            pre.next = None
            return head

        return head

——————

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 个节点。

注意：

  1. 如果两个链表没有交点，返回 null.
  2. 在返回结果后，两个链表仍须保持原有的结构。
  3. 可假定整个链表结构中没有循环。
  4. 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

我的解法：

解法满足 O(n) 时间复杂度，且仅用 O(1) 内存。

python
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
#
# @lc app=leetcode.cn id=160 lang=python3
#
# [160] 相交链表
#

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        """
        思路：
        1. 先各自遍历两个链表，分别求出两个链表的长度；
        2. 然后比较链表长度，求出链表长度差:d，接着让长的链表先走d步；
        3. 最后让两个链表同时出发，直到两者节点相同处即为相交节点。
        """
        length = list() ## 第一个为A的长度，第二个为B的长度
        ## 求两链表长度
        for node in [headA, headB]:
            tmp = 0
            while node != None:
                tmp += 1
                node = node.next
            length.append(tmp)
        node_A = headA
        node_B = headB
        d = abs(length[0] - length[1])
        ## 长的链表先走d步
        if length[0] > length[1]: ## A长
            while d > 0:
                node_A = node_A.next
                d -= 1
        else:
            while d > 0:
                node_B = node_B.next
                d -= 1
        ## 同时出发
        
        while node_A != None and node_B != None:
            if node_A == node_B:
                return node_A
            node_A = node_A.next
            node_B = node_B.next
        return None

—————

2.4 求链表是否存在环(141. 环形链表)

给定一个链表，判断链表中是否有环。

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

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

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

Yes, I can.

我的解法：

python
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

我的解法：

python
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）或指向链表中的节点。

我的解法：

python
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
### 2.6 排序链表的合并(Leetcode 21. 合并两个有序链表)

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

示例 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 均按 非递减顺序 排列

我的解法：

python
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

我的解法：

python
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
另一种不借助辅助空间的方法：

python
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:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        pre1 = 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

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        """
        思路：
        分治：每次合并lists中的不同的两个链表。
        """
        if len(lists) == 0:
            return None
        if len(lists) == 1:
            return lists[0]
        i = len(lists)
        while i > 1:
            lists.append(self.mergeTwoLists(lists.pop(0), lists.pop(0)))
            i -= 1
        
        return lists[0]