---

6-2 链表相关题目

---

版权声明：以下题目均来自 LeetCode， 仅仅提供跳转到力扣官网的链接，不在本页面出现题目内容，本文章内容禁止商业用途。

目录

小节	位置
6.2.1	链表逆序部分
6.2.2	链表删除元素的相关题目
6.2.3	链表双指针
6.2.4	链表排序部分
6.2.5	链表有环与相交

6.2.1 链表逆序部分

序号	链表逆序部分	题解
①	LeetCode 206.反转链表	6.2.1.1题解
②	LeetCode 92.反转链表 II	6.2.1.2题解
③	LeetCode 25. K 个一组翻转链表	6.2.1.3题解

6.2.1.1 反转链表

LeetCode 206.反转链表| | 返回目录6.2.1

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

思路：链表逆序在章节6-1中已经详细讲解过了。

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        '''1.递归法'''
        def recursive_func(node:ListNode):
            if node is None or node.next is None:
                return node
            
            node_new = recursive_func(node.next)
            node.next.next = node
            node.next = None

            return node_new
        
        return recursive_func(head)

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        '''2.非递归法'''
        # 在时间和内存上的消耗比 递归法 要好
        if head is None or head.next is None:
            return head
        node_A, node_B = head, head.next 
        while node_B.next is not None:
            node_C = node_B.next
            node_B.next = node_C.next
            node_C.next = node_A.next
            node_A.next = node_C
        node_B.next = node_A
        new_head = node_A.next
        node_A.next = None
        return new_head

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        '''3.非递归法-2'''
        # 速度最快，消耗内存最少
        pre, cur = None, head
        while cur:
            rest = cur.next
            cur.next = pre
            pre = cur
            cur = rest
        return pre

6.2.1.2 反转链表 II

LeetCode 92.反转链表 II| | 返回目录6.2.1

思路：区间内反转链表，最主要的是找准区间左右边界点。

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        if left == right:
            return head

        start, node_L, pre = 1, head, None
        # 先找到node_L,反转起始结点
        while start < left:
            pre = node_L
            node_L = node_L.next
            start += 1

        # 采用code最简单的那个反转方式
        # 这里不用专门找结束位置，因为可以通过控制 i 与 right 的关系来停止
        front, cur, i = None, node_L, left
        while i <= right:
            res = cur.next
            cur.next = front
            front = cur
            cur = res
            i+=1
        # 反转完成后，这一部分的起始结点就是 front结点了
        # 这一部分的尾结点，就是原始这一区间的开头：node_L
        # 还需要和 区间之后的那一部分 链接起来
        node_L.next = res

        # 还需要和 区间之前的那一部分 也链接起来  
        if pre: # pre不为初始值none，说明不是从头结点开始反转的
            pre.next = front
            return head
        else: # pre 为none，说明是从头结点开始反转的，需要更新头结点
            return front 

6.2.1.3 K个一组翻转链表

LeetCode 25. K 个一组翻转链表 | | 返回目录6.2.1

思路：反转链表的要点，还是要找准开始点和结束点。
每隔k个结点一组反转，意思是索引为 k 的倍数的结点（索引从0开始计数），是上一个区间的右边界。比如示例中的 索引2（结点3）, 索引4（结点5）；同时它也是下一次反转区间的起始结点。（如果下一次还足够反转的话）

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

        def reverse_linklist(node, k):
            # 因为该题只在有限区间内进行反转，所以需要用k来控制步长
            # 注意反转完成后，node变成这部分的尾部结点
            pre, cur = None, node 
            i = 1
            while cur and i <=k:
                res = cur.next 
                cur.next = pre 
                pre = cur 
                cur = res 
                i += 1
            return  pre 

        # 如果只有1个结点或者k=1，就不用做反转
        if head.next is None or k == 1:
            return head 

        # 先在前面设立一个哑结点
        dummy = ListNode(0, head)
        pre, start, j = dummy, head, 0
        while start:
            start = start.next 
            j += 1
            if j % k == 0:
                # 根据我们的分析，索引是k的倍数时，
                # 当前结点start是前一个区间的右边界, 也是下一个区间的起始结点
                # 待反转区间的起始结点用pre来控制
                old_begin = pre.next
                # 反转之后得到该区间的新的起始结点
                new_begin = reverse_linklist(old_begin, k)  
                # 将新的起始结点 new_begin 与 pre 进行连接              
                pre.next = new_begin
                # 反转后，老的起始结点是尾结点，自然要与右边界进行链接 
                old_begin.next = start
                # 所以 pre 更新为start的上一个结点，现在就是 old_begin
                pre = old_begin    
        # 返回哑结点之后的部分
        return dummy.next 

6.2.2 链表删除元素的相关题目

序号	链表删除元素的相关题目	题解
①	LeetCode 83.删除排序链表中的重复元素	6.2.2.1题解
②	LeetCode 82.删除排序链表中的重复元素 II	6.2.2.2题解
③	LeetCode 237.删除链表中的节点	6.2.2.3题解
④	LeetCode 203.移除链表元素	6.2.2.4题解

6.2.2.1 删除排序链表中的重复元素

LeetCode 83.删除排序链表中的重复元素 | | 返回目录6.2.2

思路 1：题目中说了已排序，已经简化了问题了，也就是重复部分只要保留第一个就行。
如果未排序的话，可能会用到哈希表。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 使用哑结点作为虚拟头结点，就可以不用单独讨论头结点是否为空的情况
        dummy = ListNode(-200)
        # 哑结点的值取-200是因为题目中的结点值范围在-100到100间
        dummy.next = head 

        pre, cur = dummy, head 
        while cur:
            # 如果当前结点值和前一个结点值相等，就删除当前结点
            if pre.val == cur.val:
                pre.next = cur.next 
            else:
                pre = cur 
            cur = cur.next 
        return dummy.next        

思路 2 ：思路 1 的 code 的想法是，每遇到一个和 pre 重复的结点，就将它删除，这样有点费时间，比如若中间有很多个重复出现的值，就要一个一个的进行删除操作。
如果直接找到重复数字区域的最末尾，从末尾处断开，这样每个区域只用执行一次断开和链接操作，理论上来说会更快一点。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:

        dummy = ListNode(-200, head)
        pre, cur = dummy, head

        while cur and cur.next :
            # 如果出现了重复，就进入下面的循环
            if cur.val == cur.next.val:
                while cur.next and cur.val == cur.next.val:
                    cur = cur.next
                # 直接将中间这段重复数值的区域全部删除
                pre.next = cur
            
            pre = cur
            cur = cur.next 

        return dummy.next

6.2.2.2 删除排序链表中的重复元素 II

LeetCode 82.删除排序链表中的重复元素 II | | 返回目录6.2.2

思路：这道题与上一道题的区别在于，若出现重复的元素，就将结点全部删除，而非简单的去重。
比较容易想到的思路是哈希表，先遍历一道元素，将value和出现的次数cnt记录入哈希表中；第二次遍历的时候就删除cnt>1的val对应的node。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        '''1. 哈希表存储'''
        hash_s = {}
        cur = head
        while cur:
            if cur.val in hash_s:
                hash_s[cur.val] +=1 
            else:
                hash_s[cur.val] = 0
            cur = cur.next

        dummy = ListNode(-200, head)
        pre, cur = dummy, head
        while cur:
            # 仍然是遇到满足删除条件，就删除该结点
            if hash_s[cur.val] > 0:
                pre.next = cur.next
            else:
                pre = cur
            cur = cur.next
        return dummy.next

思路 2：很明显哈希表的思路过于简单，可能不是它想考察的点。
由于该链表是已经有序的了，基于上一题的思路 2，这一次让pre位于重复区域的前方，而不是第一个结点即可。

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        # 因为要删除重复过的结点，所以头结点可能会变化，这里就先建立一个哑结点
        dummy = ListNode(0, head)
        pre, cur = dummy, head
        while cur.next :
            # 如果出现了重复，就进入下面的循环
            if cur.val == cur.next.val:
                # 因为我们要对比 cur 和cur.next 的值，所以while的条件要确保 cur.next 也不为None
                while cur.next and cur.val == cur.next.val:
                    cur = cur.next 
                pre.next = cur.next
                # 因为循环结束后，cur是重复区域的最后一个结点，
                # 如果它后面还有结点，就要将cur后移一位 
                if cur.next: cur = cur.next

            # 如果没有重复就正常遍历
            else:
                pre = cur
                cur=cur.next 

        return dummy.next        

6.2.2.3 删除链表中的节点

LeetCode 237.删除链表中的节点 | | 返回目录6.2.2

思路：这个题乍一看很唬人，因为平时删除结点，都是利用 pre 指针，但此题无法访问head结点，也就无法访问pre结点，感觉好像无法做。
但是题目中已经在疯狂暗示解法了：
① 题目中明确说了【注意，删除节点并不是指从内存中删除它】。意思是并不用将这个结点 node 从链表中移开。
② 题目强调了，【node 一定不是最后一个结点】。那说明什么？说明 node.next 一定存在。
回忆一下，平常删除结点是遍历到要删除的结点 node，然后 pre.next = node.next;
那么我们现在知道题目给的 node 结点，也知道一定存在 node.next 结点；
此题在暗示不用删除 node，但是又要结点少1，那明显就是要删除 node.next 这个结点：
node.next = node.next.next

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        # 先把下一个结点的值复制给node
        node.val = node.next.val
        # 然后删除 node的下一个结点
        node.next = node.next.next

6.2.2.4 移除链表元素

LeetCode 203.移除链表元素 | | 返回目录6.2.2

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

思路：比较简单,就是普通的链表删除结点操作。

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # 因为可能会删除首结点，所以这里搞一个哑结点
        dummy = ListNode(0, head)
        pre, cur = dummy, head
        while cur:
            if cur.val == val:
                pre.next = cur.next  
            else:
                pre = cur
            cur = cur.next
        return dummy.next

6.2.3 链表双指针

序号	链表双指针	题解
①	LeetCode 876.链表的中间结点	6.2.3.1题解
②	LeetCode 2095.删除链表的中间节点	6.2.3.2题解
③	LeetCode 234.回文链表	6.2.3.3题解
④	LeetCode 剑指 Offer 22.链表中倒数第k个节点	6.2.3.4题解
⑤	LeetCode 19.删除链表的倒数第 N 个结点	6.2.3.5题解
⑥	LeetCode 61.旋转链表	6.2.3.6题解
⑦	LeetCode 2.两数相加	6.2.3.7题解
⑧	LeetCode 445.两数相加II	6.2.3.8题解

6.2.3.1 链表的中间结点

LeetCode 876.链表的中间结点 | | 返回目录6.2.3

思路：这是链表快慢双指针的典型应用，即“寻找链表的中间结点”。
正常来讲，可以先遍历一遍链表，统计链表长度 N, 然后第二遍遍历 N/2 次基本就能找到中间结点。
但是使用快慢指针只需要O(N/2)即可找到中间结点。这里来稍微总结一下找链表中点的两种情况：

方案一：fast指针从头结点出发，那么slow指针最后要么正好是中间点(奇数链表),要么是中间两个结点的后一个(偶数链表) 。

slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
return slow

方案二：fast从第二个结点开始出发，slow最后要么正好是中间点(奇数链表),要么是中间两个结点的前一个(偶数链表)。

slow, fast = head, head.next
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
return slow

根据不同的需求，选用不同的fast指针起始点。

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        '''由于此题要找的是 中间or偏后的结点，所以选用上述的方案 一 '''
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

6.2.3.2 删除链表的中间节点

LeetCode 2095.删除链表的中间节点 | | 返回目录6.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 deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 因为可能会删除首结点，所以这里搞一个哑结点
        dummy = ListNode(0, head)
        # fast从头结点开始，
        pre, slow, fast = dummy, head, head

        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        # slow就是我们要删除的那个中间点    
        pre.next = slow.next
        return dummy.next

6.2.3.3 回文链表

LeetCode 234.回文链表 | | 返回目录6.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 isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast= fast.next.next 
        # 循环结束后，slow指向中间结点，或者中间两个中靠左侧的结点
        
        # 将右侧的链表进行逆序
        pre, cur = None, slow.next 
        while cur:
            rest = cur.next 
            cur.next = pre 
            pre = cur 
            cur = rest
            
        # 左右两部分进行对比
        left, right = head, pre 
        while right:
            if right.val != left.val:
                return False
            right = right.next 
            left = left.next 
        return True 
        '''
        每个循环都只遍历了 一半的链表，所以时间复杂度是O(3N/2)->O(N)
        只使用了有限个辅助变量，空间复杂度是O(1)
        '''

6.2.3.4 链表中倒数第k个节点

LeetCode 剑指 Offer 22.链表中倒数第k个节点 | | 返回目录6.2.3

思路：利用快慢指针，快指针先走K步之后（遍历完k个结点），慢指针再启动；（即快指针指向k+1结点的时候，慢指针指向head结点）
此时还剩下 n-k 个结点，等快指针遍历完序要遍历 n-k 次（此时快指针指向None结点）；
慢指针也走了 n-k 次，当前正好指向倒数第k个结点。

# 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:
        if not head or k == 0:
            return head 

        fast, slow = head, head 
        cnt = 1
        while fast:
            if cnt > k:
                # 慢指针仅在快指针超过k个点的情况下才往后遍历
                slow = slow.next 
            fast = fast.next 
            cnt += 1
        return slow 
        

6.2.3.5 删除链表的倒数第 N 个结点

LeetCode 19.删除链表的倒数第 N 个结点 | | 返回目录6.2.3

思路：和上一题的本质是一样的，先要定位到倒数第 k 个结点，然后再做删除操作。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
        dummy = ListNode(0,head)
        fast, slow, pre = head, head, dummy
        k = 1
        while fast:
            # 慢指针仅在快指针超过k个点的情况下才往后遍历
            if k > n:
                pre = pre.next
                slow = slow.next
            fast = fast.next
            k+=1
        pre.next = slow.next
        return dummy.next

6.2.3.6 旋转链表

LeetCode 61.旋转链表 | | 返回目录6.2.3

思路：观察示例可以发现，旋转后的链表，其实新的头结点，就是原来的倒数第 k 个结点。所以本质思路和上面两道题是一样的，只不过这里要注意，k 可能会大于链表长度，所以要先遍历一道链表，确定其长度，然后再对k求模。

# 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 not head or k == 0:
            return head 
        # 1.计算链表长度
        cnt, cur = 1, head 
        while cur.next:
            cnt+=1
            cur= cur.next 
        # cur 此时指向最后一个结点

        # 2.求模
        N = k % cnt 
        if N == 0:
            return head 
        
        # 3.原链表首尾相连成环
        cur.next = head
        
        # 向右移动 k 个位置，其实等效于成环之后，原倒数第k个结点做新的头结点
        # 所以问题转化为 定位倒数第 k 个结点
        fast, slow, pre = head, head, cur
        i = 1
        while i <= cnt:
            if i > N:
                pre = pre.next
                slow = slow.next 
            fast = fast.next  
            i += 1
        # 此时slow指向倒数第k个结点，可以作为新的头结点，在此处断开环
        pre.next = None 
        return slow 

6.2.3.7 两数相加

LeetCode 2.两数相加| | 返回目录6.2.3

思路：此题和 【LeetCode 415.字符串相加】这一题本质是一样的，区别在于，我们无法直接获得链表的长度。但是由于题目中提及是逆序存储的数字，且返回的也是相同形式（即逆序）相当于简化了这个题。只要每个位置对应相加即可。

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

        cur1, cur2, dummy = l1, l2, ListNode(0)
        add = 0
        pre = dummy
        while add>0 or cur1 or cur2:
            if cur1: 
                a = cur1.val 
                cur1 = cur1.next
            else:
                a = 0

            if cur2: 
                b = cur2.val 
                cur2 = cur2.next
            else:
                b = 0

            digit = (a+b+add) % 10
            add = (a+b+add-digit) // 10
            pre.next = ListNode(digit) 
            pre = pre.next 

            
        return dummy.next

6.2.3.8 两数相加II

LeetCode 445.两数相加II| | 返回目录6.2.3

思路：此题是上一题的升级版，因为顺序变成正序了。可以先反转两个链表，然后基本就和上一题差不多。

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

        def reverse_linklist(head):
            pre, cur = None, head 
            while cur:
                rest = cur.next 
                cur.next = pre
                pre = cur
                cur = rest 
            return pre

        cur1, cur2 = reverse_linklist(l1), reverse_linklist(l2)
        # pre = dummy
        '''可以选择上一题一样的做法，先逆序构造链表，然后在调用逆序函数处理一次；
        但是这样时间消耗的有点多；
        所以对code做了一点改动，生成链表的时候，直接逆序着生成'''
        pre = None
        while add>0 or cur1 or cur2:
            if cur1: 
                a = cur1.val 
                cur1 = cur1.next
            else:
                a = 0
            if cur2: 
                b = cur2.val 
                cur2 = cur2.next
            else:
                b = 0

            digit = (a+b+add) % 10
            add = (a+b+add-digit) // 10
            # pre.next = ListNode(digit) 
            cur = ListNode(digit)
            cur.next = pre
            pre = cur 

        # return reverse_linklist(dummy.next)
        return pre 

6.2.4 链表排序部分

序号	链表排序部分	题解
①	LeetCode 21.合并两个有序链表	6.2.4.1题解
②	LeetCode 23.合并 K 个升序链表	6.2.4.2题解
③	LeetCode 148.排序链表	6.2.4.3题解
④	LeetCode 147.对链表进行插入排序	6.2.4.4题解
⑤	LeetCode 328.奇偶链表	6.2.4.5题解

6.2.4.1 合并两个有序链表

LeetCode 21.合并两个有序链表| |返回目录6.2.4

思路1 ：对于两个有序部分合并成一个新的有序部分，很自然会想到归并排序中的归并操作。

# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1 and not list2:
            return None
        elif not list1:
            return list2
        elif not list2:
            return list1
        else:
            cur1, cur2 = list1, list2
            '''1.利用辅助数组'''
            # q = []
            # while cur1 and cur2:
            #     if cur1.val <= cur2.val:
            #         q.append(cur1)
            #         cur1 = cur1.next
            #     else:
            #         q.append(cur2)
            #         cur2 = cur2.next
            # while cur1:
            #     q.append(cur1)
            #     cur1 = cur1.next
            # while cur2:
            #     q.append(cur2)
            #     cur2 = cur2.next
            
            # head = q.pop(0)
            # cur = head
            # while q:
            #     node = q.pop(0)
            #     cur.next = node
            #     cur = cur.next
            # cur.next = None
            # return head
            '''2.不用辅助数组，只用几个辅助node'''
            dummy = ListNode(0)
            pre = dummy
            while cur1 and cur2:
                if cur1.val <= cur2.val:
                    pre.next = cur1
                    pre = cur1
                    cur1 = cur1.next
                else:
                    pre.next = cur2
                    pre = cur2
                    cur2 = cur2.next
            if cur1:
                # 如果此时cur1不为空，说明上面最后一个node一定来自于cur2
                pre.next = cur1
            if cur2:
                # 如果此时cur2不为空，说明上面最后一个node一定来自于cur1
                pre.next = cur2
            return dummy.next

思路2: 递归操作

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None and list2 is None:
            return None
        elif list1 is None:
            return list2
        elif list2 is None:
            return list1
        elif list1.val <= list2.val:
            # 当前list1点的值更小, 那么就让list1的后面部分去和list2做过合并
            list1.next = self.mergeTwoLists(list1.next,list2)
            return list1
        else:
            # 当前list2点的值更小, 那么就让list2的后面部分去和list1做过合并
            list2.next = self.mergeTwoLists(list1,list2.next)
            return list2

6.2.4.2 合并 K 个升序链表

LeetCode 23.合并 K 个升序链表| | 返回目录6.2.4

思路1：该题是上题的加强版，从合并2个链表变为合并k个链表。那么比较自然的想法就是，先写出合并两个链表的函数，再对链表的list进行依次两两合并即可。

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        # 直接复用上一题的合并两个链表的函数
        def merge_two_linklist(head1: Optional[ListNode], head2: Optional[ListNode]) -> Optional[ListNode]:
            if not head1 and not head2:
                return None
            elif not head1:
                return head2
            elif not head2:
                return head1
            else:
                dummy = ListNode(0)
                pre = dummy
                cur1, cur2 = head1, head2
                while cur1 and cur2:
                    if cur1.val < cur2.val:
                        pre.next = cur1
                        pre = pre.next
                        cur1 = cur1.next
                    else:
                        pre.next = cur2
                        pre = pre.next
                        cur2 = cur2.next
                if cur1:
                    pre.next = cur1
                if cur2:
                    pre.next = cur2
            return dummy.next
        
        # 思路1：从头到尾依次两两合并，耗费时间明显会很多
        res_node = lists[0]
        for i in range(1, len(lists)):
            res_node = merge_two_linklist(res_node, lists[i])
        return res_node

思路 2：两两之间先合并，然后合并后的链表再两两之间合并。
换句话说，就是使用二分法，进行递归操作，减少时间复杂度。

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        # 直接复用上一题的合并两个链表的函数
        def merge_two_linklist(head1: Optional[ListNode], head2: Optional[ListNode]) -> Optional[ListNode]:
            if not head1 and not head2:
                return None
            elif not head1:
                return head2
            elif not head2:
                return head1
            else:
                dummy = ListNode(0)
                pre = dummy
                cur1, cur2 = head1, head2

                while cur1 and cur2:
                    if cur1.val < cur2.val:
                        pre.next = cur1
                        pre = pre.next
                        cur1 = cur1.next
                    else:
                        pre.next = cur2
                        pre = pre.next
                        cur2 = cur2.next
                if cur1:
                    pre.next = cur1
                if cur2:
                    pre.next = cur2
            return dummy.next

        # 思路2： 既然是两两合并，很明显可以用二分法的思想，分而治之，用递归进行，耗时明显下降
        def merge_k_linklist(lists: List[Optional[ListNode]], Left:int, Right:int) -> Optional[ListNode]:
            if Left == Right:
                return lists[Left]
            M = (Right-Left)//2 + Left

            L_node = merge_k_linklist(lists, Left, M)
            R_node = merge_k_linklist(lists, M+1, Right)

            return merge_two_linklist(L_node, R_node)

        return  merge_k_linklist(lists, 0, len(lists)-1)

6.2.4.3 排序链表

LeetCode 148.排序链表| | 返回目录6.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 sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        def MergeTwoList(list1:Optional[ListNode], list2:Optional[ListNode]):
            if not list1 and not list2:
                return None
            elif not list2:
                return list1
            elif not list1:
                return list2
            elif list1 == list2:
                return list1 
            else:
                # 因为考虑到要使用递归操作，所以这里不创建哑结点
                # 否则可能会创建很多无用的哑结点，浪费内存
                cur1, cur2 = list1, list2 
                if cur1.val <= cur2.val:
                    head, cur1 = cur1, cur1.next 
                else:
                    head, cur2 = cur2, cur2.next
                pre = head 
                while cur1 and cur2:
                    if cur1.val <= cur2.val:
                        pre.next = cur1 
                        pre = pre.next
                        cur1 = cur1.next 
                    else:
                        pre.next = cur2 
                        pre = pre.next
                        cur2 = cur2.next 
                if cur1:
                    pre.next = cur1 
                if cur2:
                    pre.next = cur2 
            return head 

        def MergeSort(start, end):
            if start is None:
                return None
            if start.next == end:
                # 在定义的MergeSort函数的时候，规定的是end位置的结点是不取的
                # 比如最外层调用时传入的是 MergeSort(head, None)
                # 所以 start.next == end 的情况，就是在说，当前部分只有一个结点
                # 同时一定要注意，需要在这里将start彻底断开，使其真的成为一个孤立结点
                start.next = None
                return start
            
            # 然后使用快慢指针寻找中间结点
            slow, fast = start, start
            # 需要注意的是此时 fast的终点是 end，一定不要遗漏这一点
            while fast != end and fast.next != end:
                slow = slow.next
                fast = fast.next.next
            # slow指向中间结点，或者中间二结点的右边那个结点
            mid = slow
            
            left_h = MergeSort(start,mid)
            # 这里也要注意，右侧的起始点是 mid，因为根据定义左侧部分是不取mid结点的
            right_h = MergeSort(mid, end)
            return merge_two_linklist(left_h, right_h)

        # MergeSort函数也有另一种写法，即末尾head2规定可以取到的情况
        # def MergeSort(head1, head2):
        #     if head1 is None or  head1.next is None:
        #         return head1
        #     if head1 == head2:
        #     # 此时，判断是否是一个结点的条件就变为了 head1==head2
        #     # 同样要将 head1 断开
        #         head1.next = None
        #         return head1
        #     # 然后快慢结点的写法也稍作修改，找寻中间二结点中左侧的那个结点
        #     slow, fast = head1, head1.next
        #     while fast != head2 and fast.next != head2:
        #         slow = slow.next
        #         fast = fast.next.next
        #     left_end = slow
        #     right_start = slow.next
        #     # 因为规定了head2部分可以取到，所以left_end就要填入左侧的递归函数中
        #     left_h = MergeSort(head1, left_end)
        #     right_h = MergeSort(right_start, head2)
        #     return merge_two_linklist(left_h, right_h)

        return MergeSort(head, None)

6.2.4.4 对链表进行插入排序

LeetCode 147.对链表进行插入排序| |返回目录6.2.4

思路：因如果链表只有一个结点，默认有序；
所以我们从第二个结点开始遍历，每一次都需要去该结点之前，对比数字的大小，并在适当的位置进行结点插入。

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        dummy = ListNode(0, head)
        # 从第二个结点开始遍历
        tail, cur = head, head.next 
        while cur:
            if tail.val <= cur.val:
                # 先就近对比tail和cur
                tail = cur
            else:
                # 将cur从链表中先断开
                tail.next = cur.next

                # 从head开始到tail之前找
                pre = dummy
                while pre.next.val <= cur.val:
                    pre = pre.next
                # 因为上面先判断了和tail的大小关系
                # 所以此处的while循环，一定会在tail之前停下来
                # 此时 pre.next.val > cur.val
                # 所以 cur 将会在pre和pre.next中间插入
                cur.next = pre.next
                pre.next = cur
            # 更新cur
            cur = tail.next
        return dummy.next 

6.2.4.5 奇偶链表

LeetCode 328.奇偶链表| | 返回目录6.2.4

思路：创建两个头结点，一个用来连接奇数结点，另一个用来链接偶数结点。最后将两个链表合并。

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next or not head.next.next:
            # 如果结点数是0、1、2 直接返回head
            return head 
        
        # odd, even = head, head.next 
        # 创建两个哑结点，分别作为 奇偶链表的头结点
        dummy_odd = ListNode(0,head)
        dummy_even = ListNode(0,head.next)
        pre_odd, pre_even, cur = dummy_odd, dummy_even, head
        i = 1
        while cur:
            # 遍历的时候判断当前是 奇数 还是 偶数 即可
            if i % 2 == 1:
                pre_odd.next = cur 
                pre_odd = cur 
            else:
                pre_even.next = cur 
                pre_even = cur 
            cur = cur.next 
            i += 1

        pre_odd.next = dummy_even.next 
        pre_even.next = None  # 这里很容易忘记给 pre_even.next 改为 None

        return dummy_odd.next 

6.2.5 链表有环与相交

序号	链表有环与相交	题解
①	LeetCode 141.环形链表	6.2.5.1题解
②	LeetCode 142.环形链表II	6.2.5.2题解
③	LeetCode 160.相交链表	6.2.5.3题解
④	有环链表相交的情况	6.2.5.4题解

6.2.5.1 环形链表

LeetCode 141.环形链表| | 返回目录6.2.5

思路：使用快慢指针，一个跑得快，一个跑得慢，如果快指针反而与慢指针相遇，则一定是有环的。

# 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 head is None or head.next is None:
            return False
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                return True

        return False

6.2.5.2 环形链表 II

LeetCode 142.环形链表II| | 返回目录6.2.5

思路：这是上一题的升级版，不光要判断是否有环，还要返回入环的那个结点。
通过上一个题，我们已经知道如何判断有环。
在有环的情况下，开始寻找入环结点：
再设置两个游标，cur1从快慢指针相遇点开始，cur2从头结点开始，每次都只走一步，这两个游标再一次相遇的点一定是入环结点

因为fast指针是一步走两个节点，slow指针一步走一个节点，
所以 fast指针走过的节点数 = slow指针走过的节点数 2： x + y + n (z + y) = (x + y) 2 , n>=1
两边消掉一个（x+y）得: x + y = n (z + y)
求 x 的表达式的：x = n (z + y) - y = (n-1)(z + y) + z
x = (n-1)环 + z 这个等式意味着:
如果另一个指针cur2从头结点开始走，走过x步；必然和从相遇点出发的cur1指针，在环的入口处相遇!
我们不用管cur1在环内究竟转了几圈，只要关注cur2几时能遇到cur1即可。

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

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return None
        
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                # 说明有环
                cur1, cur2 = head, slow
                while cur2 != cur1:
                    cur1 = cur1.next
                    cur2 = cur2.next
                return cur2
        return None

6.2.5.3 相交链表

LeetCode 160.相交链表| | 返回目录6.2.5

题目数据保证整个链式结构中不存在环。

思路 1.比较直接的思想是用哈希表来查询。只不过这样需要消耗较多的空间。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        curA = headA
        curB = headB
        hast_a = {}
        
        while curA is not None:
            hast_a[curA] = 1
            curA=curA.next
        
        while curB is not None:
            if curB in hast_a:
                return curB
            curB=curB.next

        return None

思路 2.不用哈希表，这样比较省空间。

• 两个链表依次分别遍历，指针a负责遍历链表A，指针b负责遍历链表B，
• 若指针a指向了链表A的末尾，那么指针a就转头指向链表B，
• 同理指针b在指到末尾时也转头指向链表A，继续依次遍历。
• 当下一次指针a或者指针b其中一个又来到链表末尾，仍未找到相交结点，则确实没有相交。
• （一定要注意，指针a和指针b这个转向另外一个链表去遍历的行为，只能做一次，）
• 否则，在之前的遍历中，一定能够找到那个相交结点。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        curA = headA
        curB = headB
        # 设置统计两个游标转换链表次数的flag变量
        end_a, end_b = 0, 0
        while True:
            # 遍历过程中发现相同的结点，即可返回
            if curA == curB:
                return curA
            else:
                # 依次遍历
                curA = curA.next
                curB = curB.next
                # 当游标a来到链表的末尾，就在不触发flag的条件下，转向另一个链表
                if curA is None:
                    # end_a +1 表示链表A已经遍历完成过一次
                    end_a +=1
                    if end_a < 2:
                        curA = headB
                    else:
                        return None
                # 当游标b来到链表的末尾，就在不触发flag的条件下，转向另一个链表
                if curB is None:
                    # end_b +1 表示链表B已经遍历完成过一次
                    end_b +=1
                    if end_b < 2:
                        curB = headA
                    else:
                        return None

6.2.5.4 有环链表相交

返回目录6.2.5

那么如果问题是有环的链表相交呢？没有在LeetCode上找到对应的题目，但是这里也拿出来讨论一下。

无环链表相交的情况上一题已经讨论。
对于有环链表，首先，可以排除一个有环，一个无环的情况，这种情况必不可能相交。
所以，【有环】链表相交，一定是【两个都有环】链表的情况。
分为3种情况：
①不相交，各自有环
②共用一个环，环外相交于一个点（或刚好入环点），然后才出现环。
 这种情况，我们可以忽略那个环，就成了【从头结点到入环结点这段区间】的无环单链表相交的问题了。
③环外不相交，各自从不同的结点入环。
 这种情况，从入环结点CircleA开始沿着环移动，回到CircleA之前，会遇到另一入环结点CircleB。
可以看到，要处理这个问题，就需要用到上面两个问题作为子问题：链表求环，链表相交。
代码可能比较长，但确实逻辑上很清楚。

# coding:utf-8
from typing import List, Optional

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

class Solution:
    '''1.判断是否有环 & 求入环结点的函数'''
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return None
        
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                # 说明有环
                cur1, cur2 = head, slow
                while cur2 != cur1:
                    cur1 = cur1.next
                    cur2 = cur2.next
                return cur2
        return None

    '''2.求无环链表相交结点的函数'''
    def getIntersectionNode_No_Circle(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        # 这里采用的是哈希表方法，代码写起来简洁一点
        # 也可以使用另一种方法
        curA = headA
        curB = headB
        hast_a = dict()
        # 遍历链表a，将所有结点装入哈希表
        while curA is not None:
            hast_a.update({curA:1})
            curA=curA.next
        
        # 遍历链表b，每次都看看b的结点是否在哈希表中已经存在
        while curB is not None:
            if curB in hast_a:
                return curB
            curB=curB.next

        return None
    
    '''3.求有环链表相交结点的函数'''
    def getIntersectionNode_With_Circle(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if headA is None or headB is None:
            return None
        # 1.判断链表A和B是否有环，如果有的话返回环的结点
        Circle_A = self.detectCycle(headA)
        Circle_B = self.detectCycle(headB)
        # 2.如果两个链表都无环，就使用求无环链表相交结点的函数
        if Circle_A is None and Circle_B is None:
            return self.getIntersectionNode_No_Circle(headA, headB)
        # 3.如果一个有环一个无环，则必不可能相交，
        elif not Circle_A and Circle_B:
            return None
        elif Circle_A and not Circle_B:
            return None
        # 4.两个链表都有环
        else:
            # 4.1 两个链表入环结点一样，说明公用一个环,可以当做无环链表处理
            if Circle_A == Circle_B:
                return self.getIntersectionNode_No_Circle(headA, headB)
            # 4.2 入环结点不一样
            else:
                # 从链表A的入环结点开始在环里遍历
                cur = Circle_A
                while cur.next != Circle_A:
                    cur = cur.next
                    # 在链表A的环里果然找到链表B的入环结点
                    if cur == Circle_B:
                        # 说明两个链表的公用一个环，但入环结点不一样
                        return Circle_A
                        # 其实 Circle_B 也是相交点 , 也可以 return Circle_B
                        
                # 循环结束，没有遇到 Circle_B, 说明两个有环链表各自成环，且不相交
                return None