LeetCode Cookbook 链表习题 上篇

LeetCode Cookbook 链表习题 上篇

   开始 链表系列的习题，这章内容不是特别的难懂 就是有点不好理解，链表是很重要的一种数据结构，这次不会按照题号的大小顺序进行书写，将会按照各题的难易程度或者重要性/基础进行先后排序，继续，努力，奋斗。

876. 链表的中间结点（Base-I）

题目链接：876. 链表的中间结点
题目大意：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

例如：

输入：[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.
1
2
3
4
5

解题思路：基础题目 I 快慢指针找中间结点，不过切记这道题返回的仅为 slow，会出现 slow == fast的情况，需要在归并揭发中令fast先迈一步，会在 148. 排序链表 题中进行具体说明。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        # we do not car about fast index 
        slow,fast = head,head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow
1
2
3
4
5
6
7
8
9
10
11
12
13

141. 环形链表（Base-I 延展题目1）

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

例如：

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

解题思路： 与 876. 链表的中间结点 一摸一样了！

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

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next: return False
        # 不能原地踏步
        slow,fast = head,head
        while fast and fast.next:
            slow,fast = slow.next,fast.next.next
            if slow == fast:
                return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

142. 环形链表 II（Base-I 延展题目2）

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

例如：

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

解题思路： 在 的基础上添加了一个 while 循环。

# 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:
        slow,fast = head,head
        while fast and fast.next:
            slow,fast = slow.next,fast.next.next
            if fast == slow:
                ans = head
                while ans != slow:
                    ans,slow = ans.next,slow.next
                return ans
        return
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

206. 反转链表（Base-II）

题目链接：206. 反转链表
题目大意： 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

例如:

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

解题思路：基础题 进行翻转 注意设置 prev 空指针进行倒序牵头。

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head
        prev = None
        while head:
            tmp = head.next
            head.next = prev
            prev = head
            head = tmp
        return prev
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

24. 两两交换链表中的节点（Base-III）

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

例如：

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

解题思路：与 206. 反转链表 还是有不少的区别的，注意在 206. 反转链表 中的prev是空节点，而本题不是空节点。
具体思路见 92. 反转链表 II 中的插图。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1,head)
        cur = dummy
        while cur.next and cur.next.next:
            node1 = cur.next
            node2 = cur.next.next
            node1.next = node2.next
            node2.next = node1
            cur.next = node2
            cur = node1
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

92. 反转链表 II（Base-III 延展题目1）

题目链接：92. 反转链表 II
题目大意：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

例如：

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

解题思路： 见下图 其连接顺序是这样的： 第一步：1 -> 2 -> 4；第二步： 3 -> 2 -> 4；第三步：1 ->3 -> 2 -> 4。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if left == right: return head
        dummy = ListNode(-1,head)
        pre = dummy
        for _ in range(left-1):
            pre = pre.next
        cur = pre.next
        for _ in range(right-left):
            tmp = cur.next
            cur.next = tmp.next
            tmp.next = pre.next
            pre.next = tmp
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

61. 旋转链表（Base-III 延展题目2）

题目链接：61. 旋转链表
题目大意：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

例如：

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

解题思路： 代码注释写得已经非常详细了，这次需要进行一下链表长度的计算了。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if k == 0 or not head or not head.next: return head
        n = 1
        cur = head
        while cur.next:
            cur = cur.next
            n += 1
        # cur 走到最末尾
        add = n-k%n 
        if add == n: return head
        cur.next = head
        # 衔接上 头指针
        # 走到需要断开的地方 元素4的前面，元素3的位置
        for i in range(add):
            cur = cur.next
        # 先把 答案的头给放过去
        ans = cur.next
        # 断开！
        cur.next = None
        return ans

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

203. 移除链表元素（Base-IV）

题目链接：203. 移除链表元素
题目大意：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

例如：

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

解题思路：哑结点 典型应用。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if not head: return head
        dummy = ListNode(0,head)
        pre = dummy
        cur = head
        while cur:
            if cur.val == val: pre.next = cur.next
            else: pre = cur
            cur = cur.next
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

19. 删除链表的倒数第 N 个结点（Base-IV 延展题目1）

题目链接：19. 删除链表的倒数第 N 个结点
题目大意：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

例如：

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

解题思路： 注意与 19. 删除链表的倒数第 N 个结点 的区别，这里注意所删除的结点位置是倒着数，方法简述：
方法（一）快慢指针 是首选的方法，太巧妙了！如果要寻找倒数第n个结点，那就先令fast走n步，然后使用slow哑指针与fast指针一起走到链表尾部，这样哑指针 slow 便定位到需要删除的结点前面。
方法（二） 中规中矩 使用栈找出倒数第n个元素，扔出去。

方法（一）

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:

        # 快慢指针
        dummy = ListNode(0,head)
        fast,low = head,dummy
        for i in range(n):
            fast = fast.next
        while fast:
            low = low.next
            fast = fast.next
        low.next = low.next.next
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法（二）

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # 栈入栈出
        dummy = ListNode(0,head)
        stack = list()
        cur = dummy
        while cur:
            stack.append(cur)
            cur = cur.next
        for i in range(n):
            stack.pop()
        cur = stack[-1]
        cur.next = cur.next.next
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

237. 删除链表中的节点（Base-V）

题目链接：237. 删除链表中的节点
题目大意：有一个单链表的 head，我们想删除它其中的一个节点 node。给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

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

例如：

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

解题思路 ：这题目虽然长 但代码就两行。

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

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14

83. 删除排序链表中的重复元素（Base-V 延展题目1）

题目链接：83. 删除排序链表中的重复元素
题目大意：给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

例如：

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

解题思路： 顺着题意做下去就可以。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return head
        cur = head
        while cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

82. 删除排序链表中的重复元素 II（Base-V 延展题目2）

题目链接：82. 删除排序链表中的重复元素 II
题目大意：给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

例如：

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

解题思路： 较 83. 删除排序链表中的重复元素 稍微难一些 主要是需要在循环条件上花些功夫。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return head
        dummy = ListNode(0,head)
        cur  = dummy
        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                tmp = cur.next.val
                while cur.next and cur.next.val == tmp:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2. 两数相加（Base-VI）

题目链接：2. 两数相加
题目大意： 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

例如：

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

解题思路： 这道题非常的基础 这里记录一个在做题过程中发现的有趣的 py3 的一种连续等号的赋值方式，代码中也有体现，不过个人不喜欢多个等号写在一起，特别容易忘了，给搞错。

            a=[1,2,3]
            i=0
            i=a[i]=2
            print(a)
            输出：[1, 2, 2]
            第3行先把2赋给i，再把2赋给a[i]（a[2]），即把3替换成了2。
1
2
3
4
5
6

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        head = cur = ListNode(-1)
        carry,val = 0,0

        while carry or l1 or l2:
            val = carry
            if l1:
                val += l1.val
                l1 = l1.next
            if l2:
                val += l2.val
                l2 = l2.next
            carry,val = divmod(val,10)

            # cur.next = cur = ListNode(val)
            # 上面这一行 等价下面这两行 先赋值到最左侧
            cur.next =  ListNode(val)
            cur = cur.next
        return head.next
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

445. 两数相加 II（Base-VI 延展题目1）

题目链接：445. 两数相加 II
题目大意： 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。

例如：

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
1
2

解题思路：区别于 2. 两数相加，这里注意从右至左的一种进位累加，这里使用 栈的数据结构 将非常便于此题的处理，正好可以将链表的顺序给倒过来。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        s1,s2 = [],[]
        while l1: 
            s1.append(l1.val)
            l1 = l1.next
        while l2: 
            s2.append(l2.val)
            l2 = l2.next
        ans,carry = None,0
        while carry or s1 or s2:
            a = 0 if not s1 else s1.pop()
            b = 0 if not s2 else s2.pop()
            cur = a+b+carry
            carry = cur//10
            cur %= 10
            curNode = ListNode(cur)
            curNode.next = ans
            ans = curNode
        return ans
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

1290. 二进制链表转整数（Base-VI 延展题目2）

题目链接：345. 反转字符串中的元音字母
题目大意：给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。请你返回该链表所表示数字的 十进制值 。

例如：

输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)
1
2
3

解题思路： 数学题，控制好 指数 乘次。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        ans = 0
        while head:
            ans = ans*2 + head.val
            head = head.next
        return ans
1
2
3
4
5
6
7
8
9
10
11
12

21. 合并两个有序链表（Base-VII）

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

例如：

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

解题思路： 基础题 好好地整理出来，其实与 2. 两数相加 非常的相似，有点程序化的步骤。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        head=cur=ListNode(-1)
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return head.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

160. 相交链表（Base-VIII）

题目链接：160. 相交链表
题目大意：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。

例如：

输入：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
2
3
4
5
6

解题思路： 切片倒序

# 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) -> Optional[ListNode]:
        l1,l2 = headA,headB
        while l1 != l2:
            l1 = l1.next if l1 else headB
            l2 = l2.next if l2 else headA
        return l1
1
2
3
4
5
6
7
8
9
10
11
12
13

总结

  链表这一块的内容 刚开始做还是有些陌生的，不过通过整理发现，链表类的题目主要是 交换、拼接、删除、查找，需要对提醒进行分类汇总，在代码风格上保持一致，这样不仅利于后续代码的编写，也有益于对所学过的知识进行一个完整的、清晰的笔记思路，最后，继续加油。