datawhale组队学习笔记（2）链表
鏈表基礎知識：
①邏輯結構：集合、線性結構（一對一）、樹形結構（一對多）、圖結構（多對多）；
②存儲結構：順序存儲（順序表）、鏈式存儲（鏈式表）、索引存儲、散列存儲。
2.鏈表分類：
①單鏈表、雙鏈表、循環鏈表（單/雙）
②帶頭結點/不帶頭節點
3.（單）鏈表操作：
插入元素、刪除元素、創建單鏈表（尾插法/頭插法）
①邏輯結構：集合、線性結構（一對一）、樹形結構（一對多）、圖結構（多對多）；
②存儲結構：順序存儲（順序表）、鏈式存儲（鏈式表）、索引存儲、散列存儲。
2.鏈表分類：
①單鏈表、雙鏈表、循環鏈表（單/雙）
②帶頭結點/不帶頭節點
3.（單）鏈表操作：
插入元素、刪除元素、創建單鏈表（尾插法/頭插法）
T1 合并兩個有序鏈表
【法一】迭代（不明失敗嘗試）：將list2中的元素插入到list中
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object):def mergeTwoLists(self, list1, list2):""":type list1: Optional[ListNode]:type list2: Optional[ListNode]:rtype: Optional[ListNode]"""cur1=list1cur2=list2if not cur1:return list2elif not cur2:return list1while cur1 and cur2:if cur2.val<cur1.val: #只會出現在開頭temp=list1list1=cur2 #出現了一個我不能理解的問題就是，它倆綁定了，甚至還影響了list2的值（用逐行return看出來的），但我不能理解為什么，只能知道以后別隨便亂修改鏈表弄一大堆指針啥的，可能以后會明白吧？？list1.next=tempcur1=list1cur2=cur2.nextelse: #cur2.val>=cur1.valif cur1.next:if cur2.val>=cur1.next.val:cur1=cur1.nextelse: #cur1.val<= cur2.val <cur1.next.valtemp=cur1.nextnew=cur2cur1.next=newnew.next=tempcur1=cur1.nextcur2=cur2.nextelse: #cur1到達list1的末尾temp=cur1.nextnew=cur2cur1.next=newnew.next=tempcur1=cur1.nextcur2=cur2.nextreturn list1整體思路是：
1.初始：使用兩個指針，cur1指向list1首個結點，cur2指向list2首個節點
2.思路：將list2中的元素逐個插入到list1中（因此要逐個比較cur1和cur2指向元素的大小）
①cur1＞cur2:
把cur2指向的元素插入到cur1指向的元素之前，cur1向前移動一位（即繼續指向新list1的首個節點）
②cur1≤cur2:
再判斷cur1.next與cur2的大小關系：
（a）cur1.next≤cur2:
將cur1指針后移一位
（b）cur1.next＞cur2:
直接將cur2對應元素插入到cur1之后，cur1和cur2各后移一位
（中間套上了一層if cur1.next是因為要用到cur1.next.val，如果cur1已經指到末尾了會報錯實際上這兩個else寫的是相同的）
問題：出現了一個我不能理解的問題就是，出現了不符合邏輯的綁定？？甚至還混亂地影響了list2的值（用逐行return看出來的），反正結果就是cur2從list2上跑到新list1上去了，但我不理解為什么會跑，為什么會關聯綁定…？只能知道以后別隨便亂選擇修改鏈表的方式，弄一大堆指針啥的，可能以后會明白吧？？現在就現在想著創建新鏈表吧。。
【法二】迭代：創建一個新鏈表，輪流插入list1和list2的元素
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object):def mergeTwoLists(self, list1, list2):""":type list1: Optional[ListNode]:type list2: Optional[ListNode]:rtype: Optional[ListNode]"""prehead=ListNode(-1) #創建一個新的空頭結點prev=prehead #創建一個指針，指向空頭結點（注意：這是指針，是可以修改東西的！）while list1 and list2:if list1.val<=list2.val:prev.next=list1 #指針所指位置的nextlist1=list1.nextelse:prev.next=list2list2=list2.next #指針所指位置的nextprev=prev.next #指針后移一位，繼續修改后面if list1 is None:prev.next=list2elif list2 is None:prev.next=list1#prev.next=list1 if list1 is not None else list2return prehead.next #雖然修改的一直都是prev.next，但是因為那是指針，所以它指到之處，確實被修改了關于指針的問題，仔細想了想其實是這樣：
① 像平時（例如之前做的數組題），當我們使用指針時，通常是作為 索引 ，然后根據 nums[cur]來對應所指的數據，自然就是可以修改的，這種指針并不涉及賦值問題，因為這樣的指針是邏輯意義上的索引指針，而不是物理意義上的指針；
②關于賦值問題，比如平時我們 a=1, b=a, a=3 這樣三句的結果是b=1,a=3，就是說賦值并不會造成關聯，只是復制了一下這個值而已，這是普通的賦值語句，但是放到鏈表里，就要注意一些其他的東西了；
③在鏈表中用到的指針：
首先要想明白鏈表的數據結構，比如list1=[1,2,4]，那么:
list1.val=1, list1.next=[2,4],
list1.next.val=2, list1.next.next=[4],
list1.next.next.val=4, list1.next.next.next=None
要注意，無論是list1還是list1.next這樣，都是 ListNode()類型，可以大致類似于list1=ListNode()，也就是如果我們現在list1=cur，那么cur也是一個ListNode()類型，但實際上并沒有新實例化一個類，而是把cur真正的指到了list1這個位置上，這樣就不再是僅僅單純的賦值語句了，而是真正物理意義上的指針，它修改的是list1的.val或者next，而不是僅僅復制，因此直接return原部分就可以得到修改后的了。
【法三】遞歸(與回溯)
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object):def mergeTwoLists(self, list1, list2):""":type list1: Optional[ListNode]:type list2: Optional[ListNode]:rtype: Optional[ListNode]"""if not list1:return list2if not list2:return list1if list1.val<=list2.val:list1.next=self.mergeTwoLists(list1.next,list2)return list1else:list2.next=self.mergeTwoLists(list1,list2.next)return list2T2.移除鏈表元素
【法一】迭代：依次判斷每個元素
一個錯誤操作：（對于頭節點的錯誤處理）
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object):def removeElements(self, head, val):""":type head: ListNode:type val: int:rtype: ListNode"""cur=headif head:if head.val==val:head=head.nextwhile cur.next:if cur.next.val==val:cur.next=cur.next.nextelse: #這個else一定要注意，如果沒有else并且不縮進的話就錯啦cur=cur.nextreturn head正確操作：（對于頭節點的正確處理）
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object):def removeElements(self, head, val):""":type head: ListNode:type val: int:rtype: ListNode"""head=ListNode(next=head) #加一個頭結點pre=head #來一個指針while pre.next:if pre.next.val==val:pre.next=pre.next.nextelse:pre=pre.nextreturn head.next【法二】遞歸
1.錯誤嘗試
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object):def removeElements(self, head, val):""":type head: ListNode:type val: int:rtype: ListNode"""head=ListNode(next=head) #創建一個空頭結點cur=head #將指針指向空頭節點(這在遞歸里是絕對不可以的，因為這個指針會被反復初始化)if not cur.next:return head.nextif cur.next.val==val:cur.next=cur.next.nextreturn self.removeElements(cur,val)else:return self.removeElements(cur.next,val)-
“ 將指針指向空頭節點 ” 在遞歸里是絕對不可以的，因為這個指針會被反復初始化。
-
迭代 vs 遞歸：
? 迭代時一般來說是需要用到指針的，因為原head要用到return的時候，如果走下去就無法溯源了。遞歸時是不該用指針的，因為在每一次調用時指針會被反復初始化；然后因為它是遞歸＋回溯，它最后是會回到開頭的，所以其實也不需要弄個指針。
2.正確遞歸
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object):def removeElements(self, head, val):""":type head: ListNode:type val: int:rtype: ListNode"""if not head:return Nonehead.next=self.removeElements(head.next,val)if head.val==val:return head.nextelse:return headT3. 旋轉鏈表
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object):def rotateRight(self, head, k):""":type head: ListNode:type k: int:rtype: ListNode"""len=0cur=headif not cur:return headwhile cur.next:len+=1cur=cur.nextelse:len+=1cur.next=headcur=cur.nextk_=k%lenfor i in range(len-k_-1):cur=cur.nexthead=cur.nextcur.next=Nonereturn headT4.刪除排序鏈表中的重復元素Ⅰ
【法一】迭代
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object):def deleteDuplicates(self, head):""":type head: ListNode:rtype: ListNode"""cur=headif not cur:return headwhile cur.next:if cur.val==cur.next.val:cur.next=cur.next.nextelse:cur=cur.nextreturn head【法二】遞歸
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object):def deleteDuplicates(self, head):""":type head: ListNode:rtype: ListNode"""if not head:return headif not head.next:return headhead.next=self.deleteDuplicates(head.next) #其實基本屬于是子問題重疊＋最優子結構了if head.val==head.next.val:return head.nextelse:return head比較類似于刪除鏈表元素，遞歸解法就是“下一個是誰？”這樣的問題，不過還算是首次盲寫遞歸成功！
T5.刪除排序鏈表中的重復元素Ⅱ
【法一】迭代（兩次循環）（刪除重復元素＋刪除特定元素）
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object):def deleteDuplicates(self, head):""":type head: ListNode:rtype: ListNode"""a=[]#1 刪除重復元素（只要刪后面的就好，不需要加啞節點）cur=headif not cur:return headwhile cur.next:if cur.val==cur.next.val:a.append(cur.val)cur.next=cur.next.nextelse:cur=cur.next#2 刪除特定元素（由于首個節點也有可能被刪除，所以必須加一個啞節點）head=ListNode(next=head)cur=headwhile cur.next:if cur.next.val in a:cur.next=cur.next.nextelse:cur=cur.nextreturn head.next? 其中，也可以很明顯的感受到 “ 刪除重復元素（只要刪后面的就好，不需要加啞節點）” 和 “ 刪除特定元素（由于首個節點也有可能被刪除，所以必須加一個啞節點） ”的區別。
【法二】 迭代（一次循環）（刪除重復元素＋刪除特定元素）
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object):def deleteDuplicates(self, head):""":type head: ListNode:rtype: ListNode"""a=[]head=ListNode(next=head)cur=headif not cur.next:return cur.nextwhile cur.next.next:if cur.next.val==cur.next.next.val:a.append(cur.next.val)cur.next=cur.next.next.nextif not cur.next:breakelif cur.next.val in a:cur.next=cur.next.nextif not cur.next:breakelse:cur=cur.nextif cur.next: #用else就更帶感了if cur.next.val in a:cur.next=cur.next.nextreturn head.next? 那個地方如果用else真的非常合適！因為while…else語句，指的就是：如果while循環是因為中途break而跳出，則不會執行else語句；如果while循環是因為條件不再符合而退出，則執行else語句。而恰好，這里如果 cur.next 還不是None，則最后會因為cur.next.next==None而退出，而如果cur.next變成None了，則循環判斷語句本身會報錯，因此必須使用break語句跳出，這樣也正好與else應對應的條件相反。所以這里用while…else（配合內部break）非常合適。
【法三】迭代（一次雙重循環）（察覺＋循環直到消滅）
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object):def deleteDuplicates(self, head):""":type head: ListNode:rtype: ListNode"""a=[]head=ListNode(next=head)cur=headwhile cur.next and cur.next.next:if cur.next.val==cur.next.next.val:a=cur.next.valwhile cur.next and cur.next.val==a:cur.next=cur.next.nextelse:cur=cur.nextreturn head.next? 這種方法除了提出了明智（相對于法二）的“循環直到消滅”之外，還有很重要的一點就是，它提出了cur.next and cur.next.next這種，也就是cur.next and cur.next.val==a這種避免出錯的方式，也用不到break啦，自然也不是那么需要while…else語句這種啦。
【法四】遞歸
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object):def deleteDuplicates(self, head):""":type head: ListNode:rtype: ListNode"""if not head or not head.next:return headif head.val!=head.next.val:head.next=self.deleteDuplicates(head.next)else:move=head.nextwhile move and head.val==move.val: #這里在第一次其實是重復了的，但是更簡潔了move=move.nextreturn self.deleteDuplicates(move) #這就是主要區別，不用head.next=而用return就是刪掉自己了return head總結
以上是生活随笔為你收集整理的datawhale组队学习笔记（2）链表的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 辛巴现身泰国带货：单场销售额超8亿 光榴
- 下一篇： 【leetcode记录02】递归