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.

解题思路：基础题目 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

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

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

例如：
在这里插入图片描述

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

解题思路：与 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

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

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

例如：
在这里插入图片描述

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

解题思路：在的基础上添加了一个 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

206. 反转链表（Base-II）

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

例如:
在这里插入图片描述

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

解题思路：基础题进行翻转注意设置 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

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

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

例如：
在这里插入图片描述

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

解题思路：与 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

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 -> 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

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

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

例如：
在这里插入图片描述

输入：head = [1,2,3,4,5], k = 2
输出：[4,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 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

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

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

例如：
在这里插入图片描述

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

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

# 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

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

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

例如：
在这里插入图片描述

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

解题思路：注意与 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

方法（二）

# 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

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

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

# 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

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

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

例如：
在这里插入图片描述

输入：head = [1,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

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

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

例如：
在这里插入图片描述

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

解题思路：较 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

2. 两数相加（Base-VI）

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

例如：
在这里插入图片描述

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

解题思路：这道题非常的基础这里记录一个在做题过程中发现的有趣的 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。

# 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

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

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

例如：
在这里插入图片描述

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

解题思路：区别于 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

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

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

例如：
在这里插入图片描述

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

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

# 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

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

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

例如：
在这里插入图片描述

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

解题思路：基础题好好地整理出来，其实与 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

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 中第四个节点) 在内存中指向相同的位置。

解题思路：切片倒序

# 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

总结

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

原文链接：https://blog.csdn.net/weixin_42269028/article/details/126891377

LeetCode Cookbook 链表习题 上篇

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

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

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

206. 反转链表（Base-II）

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

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

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

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

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

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

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

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

2. 两数相加（Base-VI）

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

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

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

160. 相交链表（Base-VIII）

总结

LeetCode Cookbook 链表习题上篇