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