LeetCode-题目详解：链表

待我称王封你为后i 2023-10-04 13:27 24阅读 0赞

### 2-两数相加 ###

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]

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

示例 2：

输入：l1 = [0], l2 = [0]
    输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
    输出：[8,9,9,9,0,0,0,1]

提示：

*  每个链表中的节点数在范围 \[1, 100\] 内
 *  0 <= Node.val <= 9
 *  题目数据保证列表表示的数字不含前导零

--------------------

# 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: ListNode, l2: ListNode) -> ListNode:
      
            dummy = ListNode()  # 创建一个虚拟节点
            prev = dummy        # 创建一个prev指针，初始时指向dummy
    
            # 初始化carry和两个链表对应节点相加的值【carry代表前一个位置的进位数值】
            carry, value = 0, 0 
    
            # 下面的while循环中之所以有carry，是为了处理两个链表最后节点相加出现进位的情况【当两个节点都走完而且最后的运算并没有进位时，就不会进入这个循环】
            while carry or l1 or l2:
                
                # 让value先等于carry既有利于下面两个if语句中两个对应节点值相加，也是为了要处理两个链表最后节点相加出现进位的情况
                value = carry   
                
                # 只要其中一个链表没走完，就需要计算value的值【如果其中一个链表走完，那么下面的计算就是加总carry和其中一个节点的值，如果两个链表都没走完，那么下面的计算就是carry+对应的两个节点的值】
                if l1 is not None: 
                    value = value + l1.val      # 计算当前位的值【carry + l1.val + l2.val】
                    l1 = l1.next                # 将l1的指针位置移动到下一个节点，用于下一个循环
                if l2 is not None: 
                    value = value + l2.val      # 计算当前位的值【carry + l1.val + l2.val】
                    l2 = l2.next                # 将l2的指针位置移动到下一个节点，用于下一个循环
                
                # 如果value值大于十，则进位，需要特殊处理【如果value小于十，下面这行的操作对于carry和value的值都没有影响】
                carry, value = divmod(value, 10)    # carry代表进位数值，value代表留在当前位的数值
                
                # 尾部插入
                prev.next = ListNode(value)	#利用value的值创建一个当前节点，并让prev.next指向它
                prev = prev.next	#移动prev指针到当前节点
            
            #最后只要返回dummy的下一个节点就是我们想要的答案。
            return dummy.next

### 面试题 02.05-链表求和 【同“2-两数相加 ”】 ###

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

示例：

输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
    输出：2 -> 1 -> 9，即912

进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?

示例：

输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
    输出：9 -> 1 -> 2，即912

--------------------

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
            carry, value = 0, 0
            dummy = ListNode()
            prev = dummy
    
            while l1 or l2 or carry:
                value = carry
                if l1:
                    value += l1.val
                    l1 = l1.next
                if l2:
                    value += l2.val
                    l2 = l2.next
                
                carry, value = divmod(value, 10)
                prev.next = ListNode(value)
                prev = prev.next
    
    
            return dummy.next

### 445-两数相加 II ###

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出：7 -> 8 -> 0 -> 7

进阶：如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

--------------------

# 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: ListNode, l2: ListNode) -> ListNode:
            stack1 = []
            stack2 = []
            dummy = ListNode()
    
            # 将链表中各个节点的值压入栈中
            def push_stack(p, stack):
                while p:
                    stack.append(p.val)
                    p = p.next
                    
            push_stack(l1, stack1)
            push_stack(l2, stack2)
    
    
            # 初始化carry和两个链表对应节点相加的值【carry代表前一个位置的进位数值】
            carry, value = 0, 0 
    
            # 下面的while循环中之所以有carry，是为了处理两个链表最后节点相加出现进位的情况【当两个节点都走完而且最后的运算并没有进位时，就不会进入这个循环】
            while stack1 or stack2 or carry:
                # 让value先等于carry既有利于下面两个if语句中两个对应节点值相加，也是为了要处理两个链表最后节点相加出现进位的情况
                value = carry
                
                # 只要其中一个栈还有数据，就需要计算value的值【如果其中一个栈已经为空，那么下面的计算就是加总carry和另一个栈的值，如果两个栈都有值，那么下面的计算就是carry+对应的两个栈弹出的值】
                if stack1:
                    value = value + stack1.pop()
                if stack2:
                    value = value + stack2.pop()
                
                # 如果value值大于十，则进位，需要特殊处理【如果value小于十，下面这行的操作对于carry和value的值都没有影响】
                carry, value = divmod(value, 10)
                
                # 头部插入
                currNode = ListNode(value)
                currNode.next = dummy.next
                dummy.next = currNode
    
            return dummy.next

### 剑指 Offer 06-从尾到头打印链表 ###

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

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

限制：0 <= 链表长度 <= 10000

--------------------

#### 方法一：利用栈 ####

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def reversePrint(self, head: ListNode) -> List[int]:
            stack = []
            while head:
                stack.append(head.val)
                head = head.next
            
            result = []
            while stack:
                result.append(stack.pop())
    
            return result

### 206-反转链表 ###

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

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]

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

示例 2：  
![在这里插入图片描述][20210526170946164.png_pic_center]

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

示例 3：

输入：head = []
    输出：[]

提示：

*  链表中节点的数目范围是 \[0, 5000\]
 *  \-5000 <= Node.val <= 5000

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

--------------------

#### 方法一：利用栈 ####

# 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:
            dummy = ListNode()
            prev = dummy
            stack = []
            while head:
                stack.append(head.val)
                head = head.next
            
            while stack:
                currNode = ListNode(stack.pop())
                prev.next = currNode
                prev = prev.next
            
            return dummy.next

#### 方法二：迭代 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 2]

![在这里插入图片描述][20210526174224364.gif_pic_center]

# 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:
            dummy = ListNode()
            curr = head
    
            while curr:
                nextNode = curr.next
                curr.next = dummy.next
                dummy.next = curr
                curr = nextNode
    
            return dummy.next

#### 方法三：递归方法 ####

链表具有天然的递归性，一个链表例如 1->2->3->4->5->NULL ，可以看成头节点(节点值为 1 的节点)后面挂接一个更短的链表(缺少节点值为 1 的节点，以节点值为 2 的节点为头节点) 1->更短的链表，依次类推。如下如示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 3]  
这样的话，就可以先翻转头节点后面挂接的链表，然后把翻转后的链表的后面再挂接头节点，这样就实现了链表的翻转，如下图示：

先翻转以节点值为 2 的节点作为头节点的链表  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 4]  
将原头节点(节点值为 1 的节点)挂接在翻转之后的链表的后面  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 5]

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    '''
    1. 递归上来就先写终止条件：如果head为空或者head.next为空，返回head
    2. 新头结点newHead指向尾结点，此处进入递归，递归一直到遍历到尾结点时才会返回
    3. 每一层递归，该层递归中的head会让下一个节点指向自己，head.next.next = head；然后head自己指向空。以此达到反转的目的。
    4. 返回新链表的头结点newHead
    '''
    
    class Solution:
        def reverseList(self, head: ListNode) -> ListNode:
            
            def reverse(nodeA: ListNode)->ListNode:
                # 递归结束条件：nodeA 为最后一个节点
                if nodeA.next is None: 
                    return nodeA
                
                print("递归进入-->, nodeA.val = ", nodeA.val)
                dummy = ListNode()
                dummy.next = reverse(nodeA.next)    # 递归结束时，nodeA.next 为最后一个节点，nodeA为倒数第2个节点
                print("\n递归退出-->, dummy.next = ", dummy.next)
                
    
                nodeB = nodeA.next
    
                print("nodeA = ", nodeA)
                print("nodeB = ", nodeB)
                
                # 颠倒前后2节点连接的方向
                nodeA.next = None   # 将原来的前节点连接到后节点的链接切断
                nodeB.next = nodeA  # 将原来的后节点连接到前节点
                
    
                print("前后节点交换：")
                print("nodeB = ", nodeB)
                print("nodeA = ", nodeA)
                
    
                print("dummy.next = ", dummy.next)
    
                print()
                
                return dummy.next
            
            if head is None:
                return None
    
            return reverse(head)

输入：

[1,2,3,4,5]

输出结果：

递归进入-->, nodeA.val =  1
    递归进入-->, nodeA.val =  2
    递归进入-->, nodeA.val =  3
    递归进入-->, nodeA.val =  4
    
    递归退出-->, dummy.next =  ListNode{
        val: 5, next: None}
    nodeA =  ListNode{
        val: 4, next: ListNode{
        val: 5, next: None}}
    nodeB =  ListNode{
        val: 5, next: None}
    前后节点交换：
    nodeB =  ListNode{
        val: 5, next: ListNode{
        val: 4, next: None}}
    nodeA =  ListNode{
        val: 4, next: None}
    dummy.next =  ListNode{
        val: 5, next: ListNode{
        val: 4, next: None}}
    
    
    递归退出-->, dummy.next =  ListNode{
        val: 5, next: ListNode{
        val: 4, next: None}}
    nodeA =  ListNode{
        val: 3, next: ListNode{
        val: 4, next: None}}
    nodeB =  ListNode{
        val: 4, next: None}
    前后节点交换：
    nodeB =  ListNode{
        val: 4, next: ListNode{
        val: 3, next: None}}
    nodeA =  ListNode{
        val: 3, next: None}
    dummy.next =  ListNode{
        val: 5, next: ListNode{
        val: 4, next: ListNode{
        val: 3, next: None}}}
    
    
    递归退出-->, dummy.next =  ListNode{
        val: 5, next: ListNode{
        val: 4, next: ListNode{
        val: 3, next: None}}}
    nodeA =  ListNode{
        val: 2, next: ListNode{
        val: 3, next: None}}
    nodeB =  ListNode{
        val: 3, next: None}
    前后节点交换：
    nodeB =  ListNode{
        val: 3, next: ListNode{
        val: 2, next: None}}
    nodeA =  ListNode{
        val: 2, next: None}
    dummy.next =  ListNode{
        val: 5, next: ListNode{
        val: 4, next: ListNode{
        val: 3, next: ListNode{
        val: 2, next: None}}}}
    
    
    递归退出-->, dummy.next =  ListNode{
        val: 5, next: ListNode{
        val: 4, next: ListNode{
        val: 3, next: ListNode{
        val: 2, next: None}}}}
    nodeA =  ListNode{
        val: 1, next: ListNode{
        val: 2, next: None}}
    nodeB =  ListNode{
        val: 2, next: None}
    前后节点交换：
    nodeB =  ListNode{
        val: 2, next: ListNode{
        val: 1, next: None}}
    nodeA =  ListNode{
        val: 1, next: None}
    dummy.next =  ListNode{
        val: 5, next: ListNode{
        val: 4, next: ListNode{
        val: 3, next: ListNode{
        val: 2, next: ListNode{
        val: 1, next: None}}}}}

### 剑指 Offer 24-反转链表 【本题与 206 题相同】 ###

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL

限制：0 <= 节点个数 <= 5000

注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

### 92-反转链表 II ###

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 6]

输入：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

--------------------

#### 方法一：栈 ####

# 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: ListNode, left: int, right: int) -> ListNode:
            curr = head
            index = 1
            stack = []
            while curr:
                if left <= index <= right:
                    stack.append(curr.val)
                index += 1
                curr = curr.next
    
            j = 1
            curr = head
            while curr:
                if left <= j <= right:
                    curr.val = stack.pop()
                j += 1
                curr = curr.next
            
            return head

#### 方法二：迭代 ####

![在这里插入图片描述][20210526223938149.gif_pic_center]  
播放速度快：  
![在这里插入图片描述][20210526223729268.gif_pic_center]

# 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: ListNode, left: int, right: int) -> ListNode:
    
            dummy = ListNode()
    
            dummy.next = head
            lastNode = dummy
            curr = head
    
            index = 1
            while curr and index < left:
                index += 1
                curr = curr.next
                lastNode = lastNode.next
        
    
            tail = curr     # tail 指向已经翻转的链表的结尾【也是待翻转链表的开头节点】，用它来把已翻转的链表和剩余链表进行拼接。
            
            curr = curr.next    # 由于充当tail的节点不需要翻转，所以将curr的游标向后移动一位
            index += 1
    
            while curr and index <= right:
                print("curr.val = ", curr.val)
                nxt = curr.next
                curr.next = lastNode.next   # 将当前节点curr的next指向前段不翻转链表尾节点的next节点
                lastNode.next = curr
                tail.next = nxt # tail节点标记的是已翻转链表的结尾，一直不用动，用tail.next将已经翻转的部分与剩余部分连接起来
                curr = nxt  # 将curr的游标移动到nxt
                index += 1
    
            return dummy.next

### 143-重排链表 ###

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，  
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

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

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

--------------------

#### 方法一：线性表 ####

因为链表不支持下标访问，所以我们无法随机访问链表中任意位置的元素。

因此比较容易想到的一个方法是，我们利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可。

*  使用dummy将list中保存的各个独立节点串联起来

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def reorderList(self, head: ListNode) -> None:
            """
            Do not return anything, modify head in-place instead.
            """
            nodeList = []
        
            while head:
                curr = head
                head = head.next
                curr.next = None    # 将当前节点与后续链表切断
                nodeList.append(curr)
    
            print("nodeList = ", nodeList)
    
            dummy = ListNode()
            prev = dummy
    
            while nodeList:
                if nodeList:
                    prev.next = nodeList.pop(0)
                    prev = prev.next
                if nodeList:
                    prev.next = nodeList.pop()
                    prev = prev.next
            
            head = dummy.next

输入数据：

[1,2,3,4,5]

打印数据：

nodeList =  
    [
    	ListNode{
        val: 1, next: None}, 
    	ListNode{
        val: 2, next: None}, 
    	ListNode{
        val: 3, next: None}, 
    	ListNode{
        val: 4, next: None}, 
    	ListNode{
        val: 5, next: None}
    ]

*  将list中的各个节点串联起来

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def reorderList(self, head: ListNode) -> None:
            """
            Do not return anything, modify head in-place instead.
            """
            nodeList = []
            curr = head
    
            while curr:
                nodeList.append(curr)
                curr = curr.next
                
    
            print("nodeList = ", nodeList)
    
            i = 0
            j = len(nodeList) - 1
    
            while i < j:
                nodeList[i].next = nodeList[j]
                i += 1
                if i == j:
                    break
                nodeList[j].next = nodeList[i]
                j -= 1
            
            nodeList[i].next = None

输入数据：

[1,2,3,4,5]

打印数据：

nodeList =  
    [
    ListNode{
        val: 1, next: ListNode{
        val: 2, next: ListNode{
        val: 3, next: ListNode{
        val: 4, next: ListNode{
        val: 5, next: None}}}}}, 
    
    ListNode{
        val: 2, next: ListNode{
        val: 3, next: ListNode{
        val: 4, next: ListNode{
        val: 5, next: None}}}}, 
    
    ListNode{
        val: 3, next: ListNode{
        val: 4, next: ListNode{
        val: 5, next: None}}}, 
    
    ListNode{
        val: 4, next: ListNode{
        val: 5, next: None}}, 
    
    ListNode{
        val: 5, next: None}
    ]

### 25-K 个一组翻转链表 ###

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 7]

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

示例 2：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 8]

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

示例 3：

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

示例 4：

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

提示：

*  列表中节点的数量在范围 sz 内
 *  1 <= sz <= 5000
 *  0 <= Node.val <= 1000
 *  1 <= k <= sz

进阶：

*  你可以设计一个只使用常数额外空间的算法来解决此问题吗？
 *  你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

--------------------

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
            dummy = ListNode()
            dummy.next = head
            prev = dummy
    
            while head:
                tail = prev     # 初始化尾指针
                
                # 将尾指针移动到该小组的尾部
                for i in range(k):
                    tail = tail.next
                    if tail is None:    # 查看剩余部分长度是否大于等于 k，如果小于k，则不用再进行翻转
                        return dummy.next
                
                nex = tail.next
    
                # 翻转当前小组的所有节点
                head, tail = self.reverse(head, tail)
                
                # 把子链表重新接回原链表
                prev.next = head
                tail.next = nex
                prev = tail
                head = tail.next
            
            return dummy.next
    
        # 翻转一个子链表，并且返回新的头与尾
        def reverse(self, head, tail):
            prev = tail
            curr = head
            while curr != tail:
                nxt = curr.next
                curr.next = prev.next
                prev.next = curr
                curr = nxt
            return tail, head

### 83-删除排序链表中的重复元素 ###

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 9]

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

示例 2：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 10]

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

提示：

*  链表中节点数目在范围 \[0, 300\] 内
 *  \-100 <= Node.val <= 100
 *  题目数据保证链表已经按升序排列

--------------------

#### 方法一：一次遍历 ####

由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。

具体地，我们从指针 cur 指向链表的头节点，随后开始对链表进行遍历。如果当前 cur 与 cur.next 对应的元素相同，那么我们就将cur.next 从链表中移除；否则说明链表中已经不存在其它与 cur 对应的元素相同的节点，因此可以将cur 指向 cur.next。

当遍历完整个链表之后，我们返回链表的头节点即可。

细节：当我们遍历到链表的最后一个节点时，cur.next 为空节点，如果不加以判断，访问 cur.next 对应的元素会产生运行错误。因此我们只需要遍历到链表的最后一个节点，而不需要遍历完整个链表。

class Solution:
        def deleteDuplicates(self, head: ListNode) -> 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

# 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: ListNode) -> ListNode:
            
            dummy = ListNode()
            dummy.next = head
            prev = dummy
            curr = head
    
            while curr:
                # 如果有重复节点，则跳过当前的重复节点，使得curr指向当前重复元素的最后一个重复节点位置
                while curr.next and curr.val == curr.next.val:
                    curr = curr.next 
    
                # 如果经过上一步的while操作，prev的next不再指向原来指向的curr，则说明curr节点有重复元素，
                # 则将prev.next指向最后一个重复节点curr的下一个节点，进入下一个循环
                if prev.next != curr:
                    prev.next = curr
                # 如果经过上一步的while操作，prev的next依旧指向原来指向的curr，则说明curr节点没有重复元素，则将prev、curr分别向后移动一位，分析下一个元素
                else: 
                    prev = prev.next
                    curr = curr.next
    
    
            return dummy.next

### 82-删除排序链表中的重复元素 II ###

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 11]

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

示例 2：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 12]

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

提示：

*  链表中节点数目在范围 \[0, 300\] 内
 *  \-100 <= Node.val <= 100
 *  题目数据保证链表已经按升序排列

--------------------

在这里插入代码片

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution(object):
        def deleteDuplicates(self, head):
    
            dummy = ListNode()
            dummy.next = head
            prev = dummy
            curr = head
            
            while curr:
                # 如果有重复节点，则跳过当前的重复节点，使得curr指向当前重复元素的最后一个节点位置
                while curr.next and curr.val == curr.next.val:
                    curr = curr.next
                
                # 如果经过上一步的while操作，prev的next不再指向原来指向的curr，则说明curr节点有重复元素，
                # 则将prev.next指向最后一个重复节点curr的下一个节点【相当于跳过了剩余的最后一个重复节点】，curr移动到下一个节点位置
                if prev.next != curr:
                    prev.next = curr.next
                    curr = curr.next
                # 如果经过上一步的while操作，prev的next依旧指向原来指向的curr，则说明curr节点没有重复元素，则将prev、curr分别向后移动一位，分析下一个元素
                else:
                    prev = prev.next
                    curr = curr.next
                
    
            
            return dummy.next

### 141-环形链表 ###

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

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

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

示例 1：

![在这里插入图片描述][20210527163650932.png_pic_center]

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

示例 2：

![在这里插入图片描述][2021052716365710.png_pic_center]

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

示例 3：

![在这里插入图片描述][20210527163702108.png_pic_center]

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

提示：

*  链表中节点的数目范围是  \[ 0 , 1 0 4 \] \[0, 10^4\] \[0,104\]
 *   − 1 0 5 < = N o d e . v a l < = 1 0 5 -10^5 <= Node.val <= 10^5 −105<=Node.val<=105
 *  pos 为 -1 或者链表中的一个 有效索引 。

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

--------------------

#### 方法一：字典法/哈希表 ####

最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。

具体地，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

# 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:
            dict = {
        }
            curr = head
            while curr:
                if dict.get(curr):
                    return True
                dict[curr] = True
                curr = curr.next
            return False

class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            seen = set()
            while head:
                if head in seen:
                    return True
                seen.add(head)
                head = head.next
            return False

#### 方法二：快慢指针 ####

本方法需要读者对「Floyd 判圈算法」（又称龟兔赛跑算法）有所了解。

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

# 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:
            dummy = ListNode()
            dummy.next = head
            slow = dummy
            fast = head
    
            # 如果链表是环形链表，则fast、slow指针肯定会先后进入环，当slow与fast相遇时，while结束
            while slow != fast:
                if fast is None or fast.next is None:   # 如果该链表不是环形链表，则fast肯定会先到达尾节点，while结束
                    return False
                slow = slow.next
                fast = fast.next.next
            
            return True

# 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:
            dummy = ListNode()
            dummy.next = head
            slow = dummy
            fast = head
    
            # 如果链表是环形链表，则fast、slow指针肯定会先后进入环，当slow与fast相遇时，while结束
            while True:
                if fast is None or fast.next is None:   # 如果该链表不是环形链表，则fast肯定会先到达尾节点，while结束
                    return False
                slow = slow.next
                fast = fast.next.next
                if slow == fast:    # slow、fast第一次相遇
                    break
            
            return True

### 142-环形链表 II ###

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

示例 1：

![在这里插入图片描述][20210527163650932.png_pic_center]

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

示例 2：

![在这里插入图片描述][2021052716365710.png_pic_center]

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

示例 3：

![在这里插入图片描述][20210527163702108.png_pic_center]

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

提示：

*  链表中节点的数目范围在范围  \[ 0 , 1 0 4 \] \[0, 10^4\] \[0,104\] 内
 *   − 1 0 5 < = N o d e . v a l < = 1 0 5 -10^5 <= Node.val <= 10^5 −105<=Node.val<=105
 *  pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

--------------------

#### 方法一：字典法/哈希表 ####

最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。

具体地，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，且该节点是环入口节点。

#### 方法二：快慢指针 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 13]

Python 不支持 do〜while 语法、可以使用 while（无限循环）和 break 组合起来实现 do ~ 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:
            fast = head
            slow = head
    
            while True:
                if fast is None or fast.next is None:
                    return
                slow = slow.next
                fast = fast.next.next
                if slow == fast:    # slow、fast第一次相遇
                    break
    
            fast = head
    
            
            while True:
                if slow == fast:    # slow、fast第二次相遇
                    break
                fast = fast.next
                slow = slow.next
    
            return fast

# 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:
            fast = head
            slow = head
    
            while True:
                if fast is None or fast.next is None:
                    return
                slow = slow.next
                fast = fast.next.next
                if slow == fast:    # slow、fast第一次相遇
                    break
    
            fast = head
    
            # slow、fast第二次相遇
            while fast != slow:
                fast = fast.next
                slow = slow.next
    
            return fast

### 剑指 Offer 22-链表中倒数第k个节点 ###

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.
    
    返回链表 4->5.

--------------------

#### 方法一：栈 ####

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
            stack = []
            curr = head
            while curr:
                stack.append(curr)
                curr = curr.next
    
            for i in range(1, len(stack) + 1):
                node = stack.pop()
                if i == k:
                    return node

#### 方法二：快慢指针 ####

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    # 快慢指针
    class Solution:
        def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
            slow = head
            fast = head
    
            # 先让快指针前进k个节点
            for _ in range(k):
                fast = fast.next
            
            # 当快指针到达链表尾节点时结束，此时慢指针就是倒数第k个节点
            while fast:
                fast = fast.next
                slow = slow.next
            
            return slow

### 面试题 02.03-删除中间节点 ###

若链表中的某个节点，既不是链表头节点，也不是链表尾节点，则称其为该链表的「中间节点」。

假定已知链表的某一个中间节点，请实现一种算法，将该节点从链表中删除。

例如，传入节点 c（位于单向链表 a->b->c->d->e->f 中），将其删除后，剩余链表为 a->b->d->e->f

示例：

输入：节点 5 （位于单向链表 4->5->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

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

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

进阶：你能尝试使用一趟扫描实现吗？

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 14]

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

示例 2：

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

示例 3：

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

提示：

*  链表中结点的数目为 sz
 *  1 <= sz <= 30
 *  0 <= Node.val <= 100
 *  1 <= n <= sz

--------------------

#### 方法一：多指针 ####

# 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()
            dummy.next = head
            prev = dummy
            slow = head
            fast = head
    
            for _ in range(n):
                fast = fast.next
            
            # 将fast指针移动到链表尾节点，此时slow位于倒数第n个节点，prev位于倒数第n个节点的前一个节点
            while fast:
                fast = fast.next
                slow = slow.next
                prev = prev.next
            
            prev.next = slow.next
    
            return dummy.next

### 21-合并两个有序链表 ###

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

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 15]

输入：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 均按 非递减顺序 排列

--------------------

#### 方法一：参考归并排序中的归并步骤 ####

![在这里插入图片描述][20210527093212648.gif_pic_center]

# 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: ListNode, l2: ListNode) -> ListNode:
            dummy = ListNode()  # 哑结点
            prev = dummy        # 移动指针
    
            curr01 = l1         # 移动指针
            curr02 = l2         # 移动指针
    
    
            while curr01 and curr02:
                if curr01.val < curr02.val:
                    prev.next = curr01
                    prev = prev.next
                    curr01 = curr01.next
                else:
                    prev.next = curr02
                    prev = prev.next
                    curr02 = curr02.next
            while curr01:
                prev.next = curr01
                prev = prev.next
                curr01 = curr01.next
            while curr02:
                prev.next = curr02
                prev = prev.next
                curr02 = curr02.next
    
            return dummy.next

### 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 < = 1 0 4 0 <= k <= 10^4 0<=k<=104
 *  0 <= lists\[i\].length <= 500
 *   1 0 4 < = l i s t s \[ i \] \[ j \] < = 1 0 4 10^4 <= lists\[i\]\[j\] <= 10^4 104<=lists\[i\]\[j\]<=104
 *  lists\[i\] 按 升序 排列
 *  lists\[i\].length 的总和不超过  1 0 4 10^4 104

--------------------

#### 方法一：堆 ####

维护一个小顶堆，首先将所有链表的第一个节点加入小顶堆，每次从小顶堆中弹出一个节点node加入到最终结果的链表里，并将node的next加入到小顶堆中。

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    import heapq
    
    class Solution:
        def mergeKLists(self, lists: List[ListNode]) -> ListNode:
            if not lists:
                return None
            
            dummy = ListNode()
            heap = []
    
            # 将lists中的所有链表的第一个元素加入最小堆heap
            for idx in range(len(lists)):
                if lists[idx]:
                    heapq.heappush(heap, (lists[idx].val, idx))
                    lists[idx] = lists[idx].next
            
            print("heap = ", heap)
            
            
            cur = dummy
    
            # 最小堆heap中始终维持len(lists)个元素【比如lists中有3个链表，则heap中始终维持3个元素】
            while heap:
                # 创建一个节点
                val, idx = heapq.heappop(heap)
                cur.next = ListNode(val)
                
                # 将指针移动到下一个位置【用于添加下一个节点】
                cur = cur.next
                
                # 如果第idx个链表还有元素没加入最小堆heap，则加入新元素，维持最小堆始终有len(lists)个元素
                if lists[idx]:
                    heapq.heappush(heap, (lists[idx].val, idx))
                    lists[idx] = lists[idx].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 mergeKLists(self, lists: List[ListNode]) -> ListNode:
            if not lists:
                return None
            return self.merge(lists, 0, len(lists)-1)
    
        def merge(self, lists, left, right):
            if left == right:
                return lists[left]
            mid = (left + right) // 2
            temp1 = self.merge(lists, left, mid)
            temp2 = self.merge(lists, mid+1, right)
            return self.merge_two(temp1, temp2)
        
        def merge_two(self, temp1, temp2):
            if not temp1 and not temp2:
                return None
            if not temp1 or not temp2:
                return temp1 if temp1 else temp2
            if temp1.val < temp2.val:
                temp1.next = self.merge_two(temp1.next, temp2)
                return temp1
            else:
                temp2.next = self.merge_two(temp1, temp2.next)
                return temp2

### 234-回文链表 ###

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
    输出: false

示例 2:

输入: 1->2->2->1
    输出: true

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

--------------------

#### 方法一：将值复制到数组中后用双指针法 ####

有两种常用的列表实现，分别为数组列表和链表。如果我们想在列表中存储值，它们是如何实现的呢？

*  数组列表底层是使用数组存储值，我们可以通过索引在 O(1) 的时间访问列表任何位置的值，这是由基于内存寻址的方式。
 *  链表存储的是称为节点的对象，每个节点保存一个值和指向下一个节点的指针。访问某个特定索引的节点需要 O(n) 的时间，因为要通过指针获取到下一个位置的节点。

确定数组列表是否回文很简单，我们可以使用双指针法来比较两端的元素，并向中间移动。一个指针从起点向中间移动，另一个指针从终点向中间移动。这需要 O(n) 的时间，因为访问每个元素的时间是 O(1)，而有 n 个元素要访问。

然而同样的方法在链表上操作并不简单，因为不论是正向访问还是反向访问都不是 O(1)。而将链表的值复制到数组列表中是 O(n)，因此最简单的方法就是将链表的值复制到数组列表中，再使用双指针法判断。

*  复制链表值到数组列表中。
 *  使用双指针法判断是否为回文。

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def isPalindrome(self, head: ListNode) -> bool:
            vals = []
            curr = head
            # 将链表中的数值复制到数组中
            while curr:
                vals.append(curr.val)
                curr = curr.next
            
            # 判断数组是否是回文	
            return vals == vals[::-1]

### 148-排序链表 ###

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

示例 1：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 16]

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

示例 2：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 17]

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

示例 3：

输入：head = []
    输出：[]

提示：

*  链表中节点的数目在范围  \[ 0 , 5 ∗ 1 0 4 \] \[0, 5 \* 10^4\] \[0,5∗104\] 内
 *   − 1 0 5 < = N o d e . v a l < = 1 0 5 -10^5 <= Node.val <= 10^5 −105<=Node.val<=105

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

--------------------

方法一：最小堆

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def sortList(self, head: ListNode) -> ListNode:
            heap = []
            curr = head
            while curr:
                heapq.heappush(heap, curr.val)
                curr = curr.next
            
            dummy = ListNode()
            prev = dummy
            while heap:
                node = ListNode(heapq.heappop(heap))
                prev.next = node
                prev = prev.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 sortList(self, head: ListNode) -> ListNode:
            if not head or not head.next: return head
            left_end = self.find_mid(head)
            mid = left_end.next 
            left_end.next = None
            left, right = self.sortList(head), self.sortList(mid)
            return self.merged(left, right)
        # 快慢指针查找链表中点
        def find_mid(self, head):
            if head is None or head.next is None: return head
            slow,fast = head, head.next
            while fast is not None and fast.next is not None:
                slow=slow.next
                fast=fast.next.next
            return slow
        # 合并有序链表
        def merged(self, left, right):
            res = ListNode()
            h = res
            while left and right:
                if left.val < right.val: 
                    h.next, left = left, left.next
                else: 
                    h.next, right = right, right.next
                h = h.next
            h.next = left if left else right
            return res.next

### 160-相交链表 ###

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 18]

在节点 c1 开始相交。

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 19]

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

示例 2：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 20]

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
    输出：Reference of the node with value = 2
    输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 21]

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

注意：

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

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70 1]

# 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:
            currA = headA
            currB = headB
            
            while currA != currB:
                if currA is not None:
                    currA = currA.next
                else:
                    currA = headB
                
                if currB is not None:
                    currB = currB.next 
                else:
                    currB = headA
            
            return currA

### 剑指 Offer 52-两个链表的第一个公共节点【同“160-相交链表 ”】 ###

### 61-旋转链表 ###

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 22]

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

示例 2：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 23]

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

提示：

*  链表中节点的数目在范围 \[0, 500\] 内
 *  \-100 <= Node.val <= 100
 *   0 < = k < = 2 ∗ 1 0 9 0 <= k <= 2 \* 10^9 0<=k<=2∗109

--------------------

### 86-分隔链表 ###

### 147-对链表进行插入排序 ###

对链表进行插入排序。  
![在这里插入图片描述][2021051611525972.gif_pic_center]

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。

每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

1.  插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2.  每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3.  重复直到所有输入数据插入完为止。

示例 1：

输入: 4->2->1->3
    输出: 1->2->3->4

示例 2：

输入: -1->5->3->4->0
    输出: -1->0->3->4->5

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][202105161152105.png]

class Solution:
        def insertionSortList(self, head: ListNode) -> ListNode:
            if not head:
                return head
            
            dummyHead = ListNode(0)
            dummyHead.next = head
    
            lastSorted = head
            curr = lastSorted.next
    
            while curr:
                # 如果已排序的链表部分的尾结点的值小于当前节点的值，则直接将尾结点指针向后移动一位
                if lastSorted.val <= curr.val:
                    lastSorted = lastSorted.next
                
                # 如果链表的已排序部分的尾结点的值大于当前节点的值，则需要将当前节点插入到已排序部分中的合适位置，插入完毕后，尾结点指针也向后移动了一位
                if lastSorted.val > curr.val:
                    prev = dummyHead
                    while prev.next.val <= curr.val:    # 查询插入点
                        prev = prev.next
                    lastSorted.next = curr.next # 将已排序的链表部分的尾结点链接到“待处理节点”curr的下一个节点
                    curr.next = prev.next   # 将“待处理节点”curr的下一个节点为插入点的下一个节点
                    prev.next = curr    # 插入点的前一个节点连接到“待处理节点”curr
                
    
                curr = lastSorted.next
            
            return dummyHead.next

### 2、中频题 ###

### 2.1、203-移除链表元素 ###

### 2.2、138-复制带随机指针的链表 ###

### 2.3、面试题 02.02-返回倒数第 k 个节点 ###

### 2.4、328-奇偶链表 ###

### 2.5、24-两两交换链表中的节点 ###

### 2.6、剑指 Offer 35-复杂链表的复制 ###

### 2.7、剑指 Offer 18-删除链表的节点 ###

### 2.8、707-设计链表 ###

### 2.9、237-删除链表中的节点 ###

### 2.10、面试题 02.04-分割链表 ###

### 2.11、面试题 02.07-链表相交 ###

### 2.12、面试题 02.01-移除重复节点 ###

### 2.13、面试题 02.08-环路检测 ###

### 2.14、面试题 02.06-回文链表 ###

### 2.15、109-有序链表转换二叉搜索树 ###

### 2.16、876-链表的中间结点 ###

### 2.17、426-将二叉搜索树转化为排序的双向链表 ###

### 2.18、430-扁平化多级双向链表 ###

### 2.19、725-分隔链表 ###

### 2.20、1669-合并两个链表 ###

### 3、低频题 ###

### 3.1、369-给单链表加一 ###

### 3.2、1290-二进制链表转整数 ###

### 3.3、1721-交换链表中的节点 ###

### 3.4、1171-从链表中删去总和值为零的连续节点 ###

### 3.5、1019-链表中的下一个更大节点 ###

### 3.6、1367-二叉树中的列表 ###

### 3.7、1836-Remove Duplicates From an Unsorted Linked List ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210526154934975.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210526170941793.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[20210526170946164.png_pic_center]: https://img-blog.csdnimg.cn/20210526170946164.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20210526175924364.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[20210526174224364.gif_pic_center]: https://img-blog.csdnimg.cn/20210526174224364.gif#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210526203849840.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20210526203903620.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/2021052620391783.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20210526204156722.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[20210526223938149.gif_pic_center]: https://img-blog.csdnimg.cn/20210526223938149.gif#pic_center
[20210526223729268.gif_pic_center]: https://img-blog.csdnimg.cn/20210526223729268.gif#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20210527130543962.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20210527130547730.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20210527142628200.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20210527142632858.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20210527142801213.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 12]: https://img-blog.csdnimg.cn/2021052714280565.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[20210527163650932.png_pic_center]: https://img-blog.csdnimg.cn/20210527163650932.png#pic_center
[2021052716365710.png_pic_center]: https://img-blog.csdnimg.cn/2021052716365710.png#pic_center
[20210527163702108.png_pic_center]: https://img-blog.csdnimg.cn/20210527163702108.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 13]: https://img-blog.csdnimg.cn/20210527190053530.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 14]: https://img-blog.csdnimg.cn/20210527190211425.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 15]: https://img-blog.csdnimg.cn/2021052709090131.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[20210527093212648.gif_pic_center]: https://img-blog.csdnimg.cn/20210527093212648.gif#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 16]: https://img-blog.csdnimg.cn/20210527211216550.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 17]: https://img-blog.csdnimg.cn/20210527211220587.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 18]: https://img-blog.csdnimg.cn/20210527213142367.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 19]: https://img-blog.csdnimg.cn/20210527213149152.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 20]: https://img-blog.csdnimg.cn/20210527213155112.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 21]: https://img-blog.csdnimg.cn/20210527213200553.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210527214505780.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210527214609149.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 22]: https://img-blog.csdnimg.cn/20210527221058534.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 23]: https://img-blog.csdnimg.cn/20210527221100778.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[2021051611525972.gif_pic_center]: https://img-blog.csdnimg.cn/2021051611525972.gif#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210516115156501.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70
[202105161152105.png]: https://img-blog.csdnimg.cn/202105161152105.png