Python小白 Leetcode刷題歷程 No.21-No.25 合并兩個有序鏈表、括號生成凡蚜、合并K個排序鏈表人断、兩兩交換鏈表中的節(jié)點、K個一組翻轉(zhuǎn)鏈表
寫在前面：
作為一個計算機院的大學(xué)生朝蜘，總覺得僅僅在學(xué)校粗略的學(xué)習(xí)計算機專業(yè)課是不夠的恶迈，尤其是假期大量的空檔期，作為一個小白芹务，實習(xí)也莫得路子蝉绷，又不想白白耗費時間鸭廷。于是選擇了Leetcode這個平臺來刷題庫。編程我只學(xué)過基礎(chǔ)的C語言熔吗，現(xiàn)在在自學(xué)Python辆床，所以用Python3.8刷題庫。現(xiàn)在我Python掌握的還不是很熟練桅狠，算法什么的也還沒學(xué)讼载，就先不考慮算法上的優(yōu)化了，單純以解題為目的中跌，復(fù)雜程度什么的以后有時間再優(yōu)化咨堤。計劃順序五個題寫一篇日志，希望其他初學(xué)編程的人起到一些幫助，寫算是對自己學(xué)習(xí)歷程的一個見證了吧。
有一起刷LeetCode的可以關(guān)注我一下敛惊，我會一直發(fā)LeetCode題庫Python3解法的，也可以一起探討凸克。
覺得有用的話可以點贊關(guān)注下哦，謝謝大家闷沥！
········································································································································································
題解框架：
1.題目萎战，難度
2.題干,題目描述
3.題解代碼（Python3（不是Python，是Python3））
4.或許有用的知識點（不一定有）
5.解題思路
6.優(yōu)解代碼及分析（當(dāng)我發(fā)現(xiàn)有比我寫的好很多的代碼和思路我就會寫在這里）
········································································································································································
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
或許有用的知識點：
當(dāng)處理鏈表且需要考慮空鏈表時舆逃，我們或許可以設(shè)置一個啞結(jié)點蚂维，即dummy=LIst Node（0），dummy.next = head路狮。
解題思路：首先創(chuàng)建一個空鏈表虫啥，頂端為一個啞節(jié)點dummy，設(shè)置一個臨時指針prev指向啞節(jié)點指針奄妨。之后當(dāng)l1和l2均不為空孝鹊，將其中較小的輸入prev，并延續(xù)鏈表展蒂，當(dāng)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
或許有用的知識點：
回溯算法，在可以寫成樹形結(jié)構(gòu)的題中团赏，通過剪枝從而找到全部的解箕般，通常使用回溯算法。
解題思路：
定義一個回溯函數(shù)backtrack(cur_str,left,right)舔清，作用為當(dāng)left=right=n時丝里，將cur_str添加到res中并返回曲初；當(dāng)left<right時，顯然不符合要求杯聚，直接返回臼婆；當(dāng)left<n時，調(diào)用backtrack(cur_str+'(',left+1,right)幌绍；當(dāng)right<n時颁褂，調(diào)用backtrack(cur_str+')',left,right+1)。
最后傀广，在主函數(shù)中給回溯函數(shù)賦予初值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
或許有用的知識點：
將一個難以直接解決的大問題，分割成一些規(guī)模較小容易解決的相同問題伪冰，以便各個擊破誓酒，分而治之的方法，稱為分治算法贮聂。這道題可以使用就分治算法靠柑，時間復(fù)雜度：O(Nlogk) ，空間復(fù)雜度：O(1)寂汇。
解題思路：
聯(lián)想到第21題‘合并兩個有序鏈表’病往，這道題變成了合并K個有序鏈表。我們只需要先算前兩個鏈表的合并結(jié)果骄瓣，再將合并結(jié)果與第三個鏈表合并停巷，以此類推，共計算k-1次合并結(jié)果榕栏，最后輸出最終合并即可就行了畔勤。于是我定義了函數(shù)mergeTwoLists(l1, l2)與第21題答案一致，就很容易計算k個鏈表的合并結(jié)果扒磁。時間復(fù)雜度：O(NlogN)庆揪，空間復(fù)雜度：O(N) 。
優(yōu)解代碼及分析：
優(yōu)解代碼（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]
分析：
采用分治算法妨托，先把每兩個鏈表進行兩個鏈表的合并缸榛，再將第一遍合并的結(jié)果兩兩合并，以此類推兰伤，直到只剩一個鏈表内颗，即為所求。
No.24.兩兩交換鏈表中的節(jié)點
難度：中等
題目描述：
題解代碼（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()就是直接彈出（刪除）最后一個元素。
解題思路：
我是簡單的交換了所有相鄰兩個鏈表節(jié)點的值找前，比較好寫糟袁。但是本題要求了‘不能單純的改變節(jié)點內(nèi)部的值’，因此我的做法雖然能過躺盛，但是是不符合題意的项戴。符合題意的解法我在優(yōu)解中會給出。
優(yōu)解代碼及分析：
優(yōu)解代碼（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
分析：
判斷特解后颗品，先設(shè)置一個啞節(jié)點肯尺，令cur=head，作為當(dāng)前節(jié)點的索引躯枢；令head=dummy则吟，對dummy逐步進行鏈表節(jié)點的操作，最后輸出head.next即可锄蹂；最后設(shè)置一個stack棧氓仲，將原來cur中的’前’’后’元素放入棧，再將棧中的’后’’前’元素依次彈出到dummy的’前’’后’元素中得糜。
No.25.K個一組翻轉(zhuǎn)鏈表
難度：困難
題目描述：
題解代碼（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 **
解題思路：
和上一題思路其實類似敬扛，先設(shè)置一個啞節(jié)點dummy，再令索引鏈表p=dummy朝抖。這題我們每k個節(jié)點進行一次循環(huán)啥箭，每次循環(huán)中，先設(shè)置一個臨時鏈表tmp=head并創(chuàng)建一個空棧治宣，之后進行k次的：將tmp壓入棧中且tmp=tmp.next急侥，直到tmp=None；當(dāng)tmp=None時侮邀，如果如上循環(huán)沒有進行夠k次坏怪，將原本鏈表head返回給p.next；如果進行了K次绊茧，則將棧中元素依次彈出至索引鏈表铝宵，之后將tmp的值賦給head和p，最后輸出索引鏈表p對應(yīng)的原鏈表dummy除啞節(jié)點的dummy.next值华畏。
