Python小白 Leetcode刷题历程 No.21-No.25 合并两个有序链表、括号生成、合并K个排序链表、两两交换链表中的节点、K个一组翻转链表

写在前面：

作为一个计算机院的大学生，总觉得仅仅在学校粗略的学习计算机专业课是不够的，尤其是假期大量的空档期，作为一个小白，实习也莫得路子，又不想白白耗费时间。于是选择了Leetcode这个平台来刷题库。编程我只学过基础的C语言，现在在自学Python，所以用Python3.8刷题库。现在我Python掌握的还不是很熟练，算法什么的也还没学，就先不考虑算法上的优化了，单纯以解题为目的，复杂程度什么的以后有时间再优化。计划顺序五个题写一篇日志，希望其他初学编程的人起到一些帮助，写算是对自己学习历程的一个见证了吧。

有一起刷LeetCode的可以关注我一下，我会一直发LeetCode题库Python3解法的，也可以一起探讨。

觉得有用的话可以点赞关注下哦，谢谢大家！
········································································································································································
题解框架：

    1.题目，难度
    2.题干,题目描述
    3.题解代码（Python3（不是Python，是Python3））
    4.或许有用的知识点（不一定有）
    5.解题思路
    6.优解代码及分析（当我发现有比我写的好很多的代码和思路我就会写在这里）

········································································································································································

No.21.合并两个有序链表

难度：简单
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy=ListNode(0)
        prev=dummy
        while l1 and l2:
            if l1.val<=l2.val:
                prev.next=l1
                l1=l1.next
            else:
                prev.next=l2
                l2=l2.next
            prev=prev.next
        prev.next= l1 if l1 else l2
        return dummy.next

或许有用的知识点：
当处理链表且需要考虑空链表时，我们或许可以设置一个哑结点，即dummy=LIst Node（0），dummy.next = head。

解题思路：首先创建一个空链表，顶端为一个哑节点dummy，设置一个临时指针prev指向哑节点指针。之后当l1和l2均不为空，将其中较小的输入prev，并延续链表，当l1和l2有一个为空，则prev.next指向不为空的剩余链表。返回时返回dummy.next即可。

No.22.括号生成

难度：中等
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res,cur_str=[],""
        def backtrack(cur_str,left,right):
            if left==n and right==n:
                res.append(cur_str)
                return
            if left<right:
                return
            if left<n:
                backtrack(cur_str+'(',left+1,right)
            if right<n:
                backtrack(cur_str+')',left,right+1)
        backtrack(cur_str,0,0)
        return res

或许有用的知识点：
回溯算法，在可以写成树形结构的题中，通过剪枝从而找到全部的解，通常使用回溯算法。

解题思路：
定义一个回溯函数backtrack(cur_str,left,right)，作用为当left=right=n时，将cur_str添加到res中并返回；当left<right时，显然不符合要求，直接返回；当left<n时，调用backtrack(cur_str+'(',left+1,right)；当right<n时，调用backtrack(cur_str+')',left,right+1)。
最后，在主函数中给回溯函数赋予初值cur_str='',left=right=0即可。

No.23.合并K个排序链表

难度：困难
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        def mergeTwoLists(l1, l2):
            dummy=ListNode(0)
            prev=dummy
            while l1 and l2:
                if l1.val<=l2.val:
                    prev.next=l1
                    l1=l1.next
                else:
                    prev.next=l2
                    l2=l2.next
                prev=prev.next
            prev.next= l1 if l1 else l2
            return dummy.next
        Dummy=ListNode(0)
        if len(lists)==0:
            return Dummy.next
        Dummy.next=lists[0]
        for i in range(1,len(lists)):
            Dummy.next=mergeTwoLists(Dummy.next, lists[i])
        return Dummy.next

或许有用的知识点：
将一个难以直接解决的大问题，分割成一些规模较小容易解决的相同问题，以便各个击破，分而治之的方法，称为分治算法。这道题可以使用就分治算法，时间复杂度：O(Nlogk) ，空间复杂度：O(1)。

解题思路：
联想到第21题‘合并两个有序链表’，这道题变成了合并K个有序链表。我们只需要先算前两个链表的合并结果，再将合并结果与第三个链表合并，以此类推，共计算k-1次合并结果，最后输出最终合并即可就行了。于是我定义了函数mergeTwoLists(l1, l2)与第21题答案一致，就很容易计算k个链表的合并结果。时间复杂度：O(NlogN)，空间复杂度：O(N) 。

优解代码及分析：
优解代码（Python3.8）

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        def mergeTwoLists(l1, l2):
            dummy=ListNode(0)
            prev=dummy
            while l1 and l2:
                if l1.val<=l2.val:
                    prev.next=l1
                    l1=l1.next
                else:
                    prev.next=l2
                    l2=l2.next
                prev=prev.next
            prev.next= l1 if l1 else l2
            return dummy.next
            
        l=len(lists)
        interval=1
        if l==0:
            l0=ListNode(0)
            return l0.next
        while l>interval:
            for i in range(0,l-interval,interval*2):
                lists[i]=mergeTwoLists(lists[i], lists[i+interval])
            interval *=2
        return lists[0] 

分析：
采用分治算法，先把每两个链表进行两个链表的合并，再将第一遍合并的结果两两合并，以此类推，直到只剩一个链表，即为所求。

No.24.两两交换链表中的节点

难度：中等
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if (not head) or (not head.next):
            return head
        temp=head
        while temp and temp.next:
            temp.val,temp.next.val=temp.next.val,temp.val
            temp=temp.next.next
        return head

或许有用的知识点：
temp=list.pop()，是弹出list中最后一个元素，并储存到temp中，list.pop()就是直接弹出（删除）最后一个元素。

解题思路：
我是简单的交换了所有相邻两个链表节点的值，比较好写。但是本题要求了‘不能单纯的改变节点内部的值’，因此我的做法虽然能过，但是是不符合题意的。符合题意的解法我在优解中会给出。

优解代码及分析：
优解代码（Python3.8）

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if (not head) or (not head.next):
            return head
        dummy=ListNode(0)
        stack,cur,head=[],head,dummy
        while cur and cur.next:
            _,_ = stack.append(cur),stack.append(cur.next)
            cur=cur.next.next
            dummy.next=stack.pop()
            dummy.next.next=stack.pop()
            dummy=dummy.next.next
        if cur:
            dummy.next = cur
        else:
            dummy.next=None
        return head.next

分析：
判断特解后，先设置一个哑节点，令cur=head，作为当前节点的索引；令head=dummy，对dummy逐步进行链表节点的操作，最后输出head.next即可；最后设置一个stack栈，将原来cur中的’前’’后’元素放入栈，再将栈中的’后’’前’元素依次弹出到dummy的’前’’后’元素中。

No.25.K个一组翻转链表

难度：困难
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy=ListNode(0)
        p=dummy
        while True:
            count=k
            stack=[]
            tmp=head
            while count and tmp:
                stack.append(tmp)
                tmp=tmp.next
                count -=1
            if count:
                p.next =head
                break
            while stack:
                p.next=stack.pop()
                p=p.next
            p.next=tmp
            head=tmp
        return dummy.next

**或许有用的知识点：
while 0 = while [] = while None = while False **

解题思路：
和上一题思路其实类似，先设置一个哑节点dummy，再令索引链表p=dummy。这题我们每k个节点进行一次循环，每次循环中，先设置一个临时链表tmp=head并创建一个空栈，之后进行k次的：将tmp压入栈中且tmp=tmp.next，直到tmp=None；当tmp=None时，如果如上循环没有进行够k次，将原本链表head返回给p.next；如果进行了K次，则将栈中元素依次弹出至索引链表，之后将tmp的值赋给head和p，最后输出索引链表p对应的原链表dummy除哑节点的dummy.next值。