本系列博文為leetcode-explore-learn子欄目學習筆記，如有不詳之處，請參考leetcode官網：https://leetcode-cn.com/explore/learn/card/linked-list/

所有例題的編程語言為python

1.小結

單鏈表雙鏈表的相同點：
1.無法在常量時間內隨意訪問數據
2.能夠在o(1)時間內，在給定節點之后完成新節點的添加
3.能夠在o(1)的時間內，刪除鏈表的第一節點

區別：刪除給定節點
單鏈表無法由給定節點獲取前一個節點，因此在刪除給定節點之前必須花費o(n)的時間來找出前一個節點
雙鏈表中，可以使用“prev”字段獲取前一個節點，因此能在o(1)的時間內=刪除給定節點。

鏈表的主要優勢：刪除添加節點十分方便

2.例題

2.1合并兩個有序鏈表

leetcode 21
將兩個升序鏈表合并為一個新的升序鏈表并返回。

思路1:迭代

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def mergeTwoLists(self, l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""if l1==None or l2==None:return l1 if l1 else l2res_head=ListNode(0)res_curr_node=res_headwhile(l1 and l2):if l1.val<=l2.val:l1_next_node=l1.nextl1.next=Noneres_curr_node.next=l1l1=l1_next_noderes_curr_node=res_curr_node.nextelse:l2_next_node=l2.nextl2.next=Noneres_curr_node.next=l2l2=l2_next_noderes_curr_node=res_curr_node.nextif l1:res_curr_node.next=l1if l2:res_curr_node.next=l2return res_head.next    

精簡寫法：

class Solution(object):def mergeTwoLists(self, l1, l2):if l1==None or l2==None:return l1 if l1 else l2res_head=ListNode(0)res_curr_node=res_headwhile(l1 and l2):if l1.val<=l2.val:res_curr_node.next=l1l1=l1.nextelse:res_curr_node.next=l2l2=l2.nextres_curr_node=res_curr_node.nextres_curr_node.next=l1 if l1 else l2   return res_head.next

思路2:遞歸

遞歸最重要的是遞歸出口

class Solution(object):def mergeTwoLists(self, l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""if l1==None:return l2elif l2==None:return l1elif l1.val<=l2.val:l1.next=self.mergeTwoLists(l1.next,l2)return l1       # 由頂向下時，已經決定了第一個節點是誰，遞歸得到最底端時，直接將長鏈表的剩余部分鏈接回已經排序好的鏈表中。else:l2.next=self.mergeTwoLists(l1,l2.next)return l2

2.2 兩數相加

給出兩個 非空的鏈表 來表示兩個 非負整數。其中，他們各自的位數是按照 逆序 方式存儲的，并且每個節點只能存儲一位 數字。

如果，我們將這兩個數相加起來，返回一個新的鏈表表示它們的和

可以假設除了數字0之外，兩個數字都不會以0開頭

思路：逆序存儲簡化了問題，直接遍歷兩個鏈表的對位元素，相加后維護一個進位標志flag。
冗余

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def addTwoNumbers(self, l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""flag=0res_head=ListNode(0)res_cur_node=res_headwhile(l1 and l2):sum_num=l1.val+l2.val+flagflag=sum_num//10res_cur_node.next=ListNode(sum_num%10)res_cur_node=res_cur_node.nextl1=l1.nextl2=l2.nextwhile(l1):#print(l1.val)sum_num=l1.val+flagflag=sum_num//10res_cur_node.next=ListNode(sum_num%10)res_cur_node=res_cur_node.nextl1=l1.nextwhile(l2):#print(l2.val)sum_num=l2.val+flagflag=sum_num//10res_cur_node.next=ListNode(sum_num%10)res_cur_node=res_cur_node.nextl2=l2.nextif flag:res_cur_node.next=ListNode(flag)return res_head.next

精簡

class Solution(object):def addTwoNumbers(self, l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""carry=0res_head=ListNode(0)res_cur_node=res_headwhile(l1 or l2 or carry):if l1:carry+=l1.vall1=l1.nextif l2:carry+=l2.vall2=l2.nextcarry,val=divmod(carry,10)res_cur_node.next=ListNode(val)res_cur_node=res_cur_node.nextreturn res_head.next

2.3 扁平化多級雙向鏈表

多級雙向鏈表中，除了指向下一個節點和前一個節點的指針外，它還有一個子鏈表指針，可能指單獨的雙向鏈表。這些子鏈表也可能有一個或多個自己的子項。一次類推，生成多級數據結構 。

給出位于鏈表第一級的頭節點，請扁平化鏈表，使所有的節點出現子啊單級雙鏈表中。

直覺：采用遞歸的方式求解，可每個節點該如何處理呢：
新建一個res_head,res_head下一個節點應該為curr_node.child,curr_node.next,

官方思路遞歸：扁平化處理可以看作對二叉樹進行先序遍歷，child作為二叉樹中的指向座子樹的left指針，next可以看作二叉樹中的right指針。
難點：深度優先遍歷到了末尾該如何讓扁平化操作？
flatten_dfs(prev, curr)接收兩個指針作為函數參數，并返回扁平化鏈表中的尾部指針。curr指向需要扁平化的子列表，prev指向curr元素的前一個元素。
在dfs函數中首先要建立prev和curr的雙向鏈接
然后對左子樹進行操作dfs(curr,cuur.child)其將返回扁平化子列表的尾部元素，再調用dfs(tail,curr.next)對右子樹進行操作。注意點：
1.在進行左子樹操作時，需要先保存curr.next的信息
2.在扁平化child指針所指向的列表之后，應該刪除child指針

"""
# Definition for a Node.
class Node(object):def __init__(self, val, prev, next, child):self.val = valself.prev = prevself.next = nextself.child = child
"""class Solution(object):def flatten(self, head):""":type head: Node:rtype: Node"""if head==None:return headdummy_head=Node(None,None,head,None)self.flatten_dfs(dummy_head,head)dummy_head.next.prev=Nonereturn dummy_head.nextdef flatten_dfs(self,prev,curr):if curr==None:return prevcurr.prev=prevprev.next=currtempNext=curr.nexttail=self.flatten_dfs(curr,curr.child)curr.child=Nonereturn self.flatten_dfs(tail,tempNext)

官方思路迭代：

2.4 復制帶隨機指針的鏈表

給定一個鏈表，每個節點包含一個額外增加的隨機指針，該指針可以指向鏈表中的任何節點或空節點
編程實現這個鏈表的深度拷貝

難點：新建節點，很簡單，隨機節點該如何指向？

先遍歷一遍形成一個單鏈表，再遍歷一遍原鏈表找到帶隨機指針的節點，在單鏈表中找到對應的節點，難的是對應節點怎么找，因為，指針存的是地址，在新鏈表中并不知道該指向哪一個？解決方案–維護一張map映射表，每個節點對應的新節點，因此便可以找到對應的節點。

"""
# Definition for a Node.
class Node:def __init__(self, x, next=None, random=None):self.val = int(x)self.next = nextself.random = random
"""class Solution(object):def copyRandomList(self, head):""":type head: Node:rtype: Node"""if head==None:return NonevisitedHash={}res_head=Node(0)res_cur_node=res_headcur_node=headwhile(cur_node):node=Node(cur_node.val,None,None)res_cur_node.next=nodevisitedHash[cur_node]=noderes_cur_node=res_cur_node.nextcur_node=cur_node.nextcur_node=headres_cur_node=res_head.nextwhile(cur_node):if cur_node.random:node=visitedHash[cur_node.random]res_cur_node.random=nodecur_node=cur_node.nextres_cur_node=res_cur_node.nextreturn res_head.next

參考官網給題解：遞歸
帶隨機指針的鏈表可以看作一張圖，要做的是遍歷整張圖，并拷貝它。拷貝的意思是每當遇到一個新的未訪問過的節點，需創造新的節點。在回溯的過程中記錄訪問過的節點，否則因為隨機指針存在，會導致死循環。

"""
# Definition for a Node.
class Node:def __init__(self, x, next=None, random=None):self.val = int(x)self.next = nextself.random = random
"""class Solution(object):def __init__(self):self.visitedHash={}def copyRandomList(self, head):""":type head: Node:rtype: Node"""if head==None:return Noneif head in self.visitedHash:return self.visitedHash[head]node=Node(head.val,None,None)self.visitedHash[head]=nodenode.next=self.copyRandomList(head.next)node.random=self.copyRandomList(head.random)return node

2.5 旋轉鏈表

給定一個鏈表，將鏈表的每個節點向右移動k個位置，其中k是非負數。

思路1:和旋轉數組一樣，每次右移一位，移動K次即可

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def rotateRight(self, head, k):""":type head: ListNode:type k: int:rtype: ListNode"""if head==None or head.next==None:return headl=0cur_node=headwhile(cur_node):l+=1cur_node=cur_node.nextk=k%ldef rotate_one_step(head):pre_pre_node=Nonepre_node=headcur_node=head.nextwhile(cur_node):pre_pre_node=pre_nodepre_node=cur_nodecur_node=cur_node.nextpre_pre_node.next=Nonepre_node.next=headreturn pre_nodewhile(k>0):head=rotate_one_step(head)k-=1return head         

思路2: 移動k次，就是將倒數的k個節點相對順序不變的移動到鏈表的頭部。所以從鏈表的head開始，往后找到L-k個節點，將后半部分移動到鏈表的前半部分。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def rotateRight(self, head, k):""":type head: ListNode:type k: int:rtype: ListNode"""if head==None or head.next==None:return headl=0cur_node=headwhile(cur_node):l+=1cur_node=cur_node.nextk=k%l# 首尾相連pre_node=Nonecur_node=headwhile(cur_node):pre_node=cur_nodecur_node=cur_node.nextpre_node.next=head# 尋找切割點cur_node=headfor _ in range(1,l-k): #[0,l-k-1]cur_node=cur_node.next# 確定的新的頭部new_head=cur_node.nextcur_node.next=Nonereturn new_head