206反轉鏈表【鏈表結構基礎】

• 設定一個前結點和后結點。

class Solution(object):def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""pre=Nonecur=headwhile cur!=None:temp=cur.nextcur.next=prepre=curcur=tempreturn pre

21合并兩個有序鏈表【遞歸】

我的答案【錯誤】

class Solution(object):def mergeTwoLists(self, list1, list2):""":type list1: Optional[ListNode]:type list2: Optional[ListNode]:rtype: Optional[ListNode]"""resol=ListNode()while list1!=None and list2!=None:if list1.val<=list2.val:resol.next=ListNode(list1.val)else:resol.next=ListNode(list2.val)list1=list1.nextlist2=list2.nextwhile list1!=None:resol.next=ListNode(list1.val)while list2!=None:resol.next=ListNode(list2.val)return resol.next

自己修改【超出時間限制】

class Solution(object):def mergeTwoLists(self, list1, list2):""":type list1: Optional[ListNode]:type list2: Optional[ListNode]:rtype: Optional[ListNode]"""resol=ListNode(0)temp=resolwhile list1 and list2:if list1.val<=list2.val:resol.next=list1list1=list1.next################else:resol.next=list2list2=list2.next################resol=resol.next######################其實是不斷增加結點的過程，所以記得更新while list1:resol.next=list1while list2:resol.next=list2return temp.next

在官方那里學到的【然后自己復寫,錯誤】

class Solution(object):def mergeTwoLists(self, list1, list2):""":type list1: Optional[ListNode]:type list2: Optional[ListNode]:rtype: Optional[ListNode]"""if list1 is None:return list2elif list2 is None:return list1else:if list1.val<list2.val:list1.next=mergeTwoLists(self,list1.next,list2)###如果只改mergeTwoLists(self,list1.next,list2)也是可以編譯通過的，運行成功，else這里的邏輯也可以修正一下return list1else:list2.next=mergeTwoLists(self,list2.next,list1)return list2

對照官方【自己修改】

class Solution(object):def mergeTwoLists(self, list1, list2):""":type list1: Optional[ListNode]:type list2: Optional[ListNode]:rtype: Optional[ListNode]"""if list1 is None:return list2elif list2 is None:return list1elif list1.val<list2.val:list1.next=self.mergeTwoLists(list1.next,list2)########函數的調用return list1else:list2.next=self.mergeTwoLists(list2.next,list1)########函數的調用return list2

160相交鏈表【未理解題目目的】

• 我看輸入部分都已經給了要輸出的結果了，就不明白這題目的是要做什么。

在b站up那里學到的【然后自己復寫,錯誤】

class Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""p=headA,q=headBwhile(p!=q):p ? p.next : headBq ? q.next : headAprint("p.val")

【超出時間限制】

class Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""p=headAq=headBwhile(p!=q):if p.next !=None:p=p.nextelse:p=headBif q.next!=None:q=q.nextelse:q=headAreturn p

對照官方【自己修改】

class Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""p=headA ####p,q=headA,headB這樣可以q=headB ####p=headA,q=headB會報錯while(p!=q):p = p.next if p else headBq = q.next if q else headAreturn p

19刪除鏈表的倒數第 N 個結點

看完官方解題思路【自己復寫，錯誤】

class Solution(object):def removeNthFromEnd(self, head, n):""":type head: ListNode:type n: int:rtype: ListNode"""p=headfor i in range(n+1):p=p.nextq=headwhile p!=None:q=q.nextp=p.next###########【這里不能少啊！】q.next=q.next.nextreturn head

報錯信息

• 查閱資料后發現：【self.head是指向第一個元素的，此時為None,所以沒有next屬性，自然就會報錯。因此第一個結點需要特殊處理，我們一般通過增加頭結點的方式來避免這種特殊處理。】

第一遍修改

• 發現當鏈表有n個元素時，無法刪除倒數第n個元素。
• 【沒有考慮到第一個結點的特殊性。】

class Solution(object):def removeNthFromEnd(self, head, n):""":type head: ListNode:type n: int:rtype: ListNode"""p=ListNode(0, head)#################for i in range(n+1):p=p.nextq=ListNode(0, head)#################while p!=None:q=q.nextp=p.nextq.next=q.next.next#########無法刪除倒數第n個元素return head

第二遍修改

class Solution(object):def removeNthFromEnd(self, head, n):""":type head: ListNode:type n: int:rtype: ListNode"""dummy=ListNode(0, head)p=dummyfor i in range(n+1):p=p.nextq=dummywhile p!=None:q=q.nextp=p.nextq.next=q.next.nextreturn dummy.next 

148排序鏈表

我的答案【冒泡排序：最小的負數輸出時變為0】

class Solution(object):def sortList(self, head):""":type head: ListNode:rtype: ListNode"""dummy=ListNode(0,head)q=dummywhile q.next!=None:p=dummywhile p.next!=None:if p.val>p.next.val:temp=p.valp.val=p.next.valp.next.val=tempp=p.nextq=q.nextreturn dummy.next

官方答案【歸并排序】

class Solution(object):def sortList(self, head):def sortFunc(head, tail):if not head:return headif head.next == tail:head.next = Nonereturn headslow = fast = headwhile fast != tail:slow = slow.nextfast = fast.nextif fast != tail:fast = fast.nextmid = slowreturn merge(sortFunc(head, mid), sortFunc(mid, tail))######合并兩個升序鏈表，但是長度差最多為1    def merge(head1, head2):dummyHead = ListNode(0)temp, temp1, temp2 = dummyHead, head1, head2while temp1 and temp2:if temp1.val <= temp2.val:temp.next = temp1temp1 = temp1.nextelse:temp.next = temp2temp2 = temp2.nexttemp = temp.nextif temp1:temp.next = temp1elif temp2:temp.next = temp2return dummyHead.nextreturn sortFunc(head, None)