写出一段代码将链表中的两个节点位置互换位置_面试 leetcode 算法专题系列（二）—— 链表...
前言：只照著常考題去刷題確實是一種方法。但調研之后發現自己還是考慮不周，刷題刷的不應該是題，而是解題的思路和熟練程度。于是我決定重新組織一下刷題筆記的講解順序，不再以面試常考題來刷。而是以面試出題頻率，方法思路類型，和難度等要素來綜合排序。每一次分享我們會沿著一個主題展開它的各種變體，確保一次性能吃透與它類似的題目。往后我們會確定主題，對該主題下問題一步步分解，然后確定模板、舉一反三去做題。而不是簡單無腦地刷題。
這一次，我們的主題是鏈表。本文會覆蓋以下三個內容：
一、面試常考鏈表題調研
首先，我們點進 Leetcode 頁面，依次點題庫，標簽，鏈表，出現頻率，便可以看到以下的題目排序。我們可以發現，鏈表類題目相對都是比較容易，簡單中等題五五開，很少有困難題目。所以它這里更多的是考察一個代碼的熟練度。比如對邊界的處理，對指針的操作等。
Leetcode 鏈表?leetcode-cn.com二、鏈表常見考察點
鏈表和數組統稱為線性表。數組所有元素都儲存在一段連續的內存中，具有通過下標訪問數據的能力 O(1)。但這也讓它擴容和刪除元素的成本變得很高 O(n)。
因為擴容要新申請一塊更大的內存，復制所有元素，再刪除原來的內存。
而刪除插入元素需要把該元素位置之后的其它元素都往前或往后挪一個位置，若插入時剛好分配的內存滿了，還要重新進行擴容操作。
對比之下，鏈表由多個結點組成，每個結點包含了數據和指針。數據指向具體的內存塊，而指針指向一個結點的內存地址。一般鏈表用一個 head 頭結點指針來表示。
鏈表的好處是插入刪除的空間復雜度是 O(1)，但是訪問某個結點的空間復雜度是 O(n)。
設計鏈表
class ListNode:def __init__(self, x):self.val = xself.next = Noneclass MyLinkedList:def __init__(self):"""Initialize your data structure here."""self.head = Noneself.length = 0def print(self):node = self.headwhile node:print(node.val, end = " ")node = node.nextprint()def get(self, index: int) -> int:"""Get the value of the index-th node in the linked list. If the index is invalid, return -1."""if index >= self.length:return -1prev = self.headcurr = self.headfor _ in range(index):prev = currcurr = curr.nextreturn curr.valdef addAtHead(self, val: int) -> None:"""Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list."""self.length += 1if not self.head:self.head = ListNode(val)else:new_head = ListNode(val)new_head.next = self.headself.head = new_headdef addAtTail(self, val: int) -> None:"""Append a node of value val to the last element of the linked list."""self.length += 1if not self.head:self.head = ListNode(val)else:tail = self.headwhile tail.next:tail = tail.nexttail.next = ListNode(val)def addAtIndex(self, index: int, val: int) -> None:"""Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted."""if index > self.length:returnif index == 0:new = ListNode(val)new.next = self.headself.head = newself.length += 1returnif index == self.length:self.addAtTail(val)returnprev = self.headcurr = self.headfor _ in range(index):prev = currcurr = curr.nextprev.next = ListNode(val)prev = prev.nextprev.next = currself.length += 1def deleteAtIndex(self, index: int) -> None:"""Delete the index-th node in the linked list, if the index is valid."""if index < self.length:self.length -= 1if index == 0:prev = self.headself.head = self.head.nextprev.next = Nonedel prevreturnprev = self.headcurr = self.headfor _ in range(index):prev = currcurr = curr.nextprev.next = curr.nextcurr.next = Nonedel curr1. 節點的返回 （全 8 道題）
題目一般要你返回鏈表中滿足某個條件的節點，大都可以使用雙指針的思想。
- 返回倒數第 k 個節點的值
倒數第 k 個節點，意味著某個指針要再走 k 步才會到結尾。怎樣知道一個結點它的位置距離尾部有 k 步呢？我們可以用兩個指針before，after 分別指向頭結點。其中 before 結點不動，after 結點走 k 步后，才讓 before 結點開始往后走。二者的步伐都一致，二者就會相隔 k 步。當 after 結點走到結尾的時候，before 結點所在的位置剛好是要返回的結點。代碼如下：
# Definition for singly-linked list.- 鏈表中倒數第 k 個節點往后的鏈表
該題與上一題無差別，只是返回的內容是指針而不是值。這里要注意一下，以防 k 過大溢出， k 的取值要與鏈表的長度取膜。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:n = 0node = headwhile node:node = node.nextn += 1k = k % (n+1)if n < 2:return headbefore = after = headfor i in range(k):after = after.nextwhile after:after = after.nextbefore = before.nextreturn before- 鏈表的中間結點
這里同樣是兩個指針，不過是一快一慢。快指針每次走兩步，慢指針每次走一步。兩個指針同時從 head 開始走。如果鏈表長度為奇數，中點節點兩邊節點個數相等，最終快指針的下一個為空時停止，直接返回慢指針。如果鏈表長度為偶數，則沒有中間節點能平分鏈表，我們取右邊的最左邊節點作為返回，即此時快指針為空時，返回慢指針。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def middleNode(self, head: ListNode) -> ListNode:if not head:return headfast, slow = head, headwhile fast and fast.next:fast = fast.next.nextslow = slow.nextreturn slow環形鏈表
也是雙指針。我們考慮讓快指針比慢指針的步伐快走一步，即快指針每次走兩步，慢指針每次走一步。這樣快指針會先進入環中，當慢指針葉進入環后，與快指針剛好相差 k 個結點，設 n1 為環外的結點個數，n2 為構成環的結點個數，則很容易得到 n2 - n1 = k。當它們繼續在環中一快一慢的步伐一直前行，由于每次快指針都能追上慢指針一個結點，所以它們之間的差距每次迭代都會小一步，即 k 會越來越小。直到 k == 0 時，二者相遇，說明有環。反過來想，若快指針能走到一個盡頭，即它走到的位置下一個結點為空，則說明沒有環。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def detectCycle(self, head: ListNode) -> ListNode:slow, fast = head, headwhile 1:if not fast or not fast.next:return Falsefast, slow = fast.next.next, slow.nextif fast == slow:breakreturn True環形鏈表 Ⅱ
如果我們要找入環點的位置，根據前面的公式，慢指針剛進入環中的時候，滿足 n2 - n1 = k。若快指針降到每次一步的速度往前走 n2 - k 步，則剛好獲得 head 到入環口的結點個數 n1。第一次快慢指針相遇時，慢指針走了 k + n1 = n2 步，所以要返回入環口，我們只需要在快慢指針相遇的時候，讓快慢指針再以每次一步的步頻往前走，直到二者第二次相遇。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def detectCycle(self, head: ListNode) -> ListNode:slow, fast = head, headwhile 1:if not (fast and fast.next):return Nonefast, slow = fast.next.next, slow.nextif fast == slow:breakslow = headwhile fast != slow:fast = fast.nextslow = slow.nextreturn slow- 兩個鏈表的第一個公共節點，鏈表相交
公共結點有一個特征是，它離尾部的距離是一樣的。對于長鏈表 B 來說，它要比短鏈表 A 事先多走 k 步才能到公共結點。這個 K 步，剛好是鏈表 B 比 鏈表 A 多出來的長度。要怎樣獲得這個 K 呢？一種簡單方法是分別算兩個鏈表的長度，相減便是。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:if not headA or not headB:return Nonedef get_length(head):n = 0while head:head = head.nextn += 1return nA_length, B_length = get_length(headA), get_length(headB)if A_length <= B_length:headA, headB = headB, headAfor _ in range(abs(A_length - B_length)):headA = headA.nextwhile headA and headB and headA != headB:headA = headA.nextheadB = headB.nextif not headA or not headB:return Nonereturn headA一般人很少會想到這題也可以用快慢指針來做。一開始從兩個鏈表以1的步伐分別各走一個指針。當其中一個先到達尾部時，讓它下一步往后跳到另一個鏈表的頭結點繼續走，當另一個指針走到尾部時，同理。最終當它們第一次重疊時，返回的便是最開頭的公共節點。問題是我們要如何判斷它沒有公共交點呢？也簡單。當其中一個節點能夠兩次走到結尾，則說明沒有公共交點。我們設立兩個 Bool 變量去分別記錄兩個指針是否走過結尾。若走過，就返回 None。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:if not headA or not headB:return Nonep1, p2 = headA, headBp1_first_None, p2_first_None = False, Falsewhile p1 != p2:p1, p2 = p1.next, p2.nextif not p1:if p1_first_None:return Nonep1 = headBp1_first_None = Trueif not p2:if p2_first_None:return Nonep2 = headAp2_first_None = Truereturn p1- 2. 節點的刪除 （全 9 道題）
Leetcode 還會考核滿足某一條件的節點的刪除。如上圖所示。節點刪除考察的是要如何改變鏈表的指針域，以達到刪除的目的。
刪除鏈表中的節點（只給要刪除節點），刪除中間節點
我們先從最簡單的來。一種刪除節點的題是它不給你鏈表，只給你某個要刪除當前節點。最直接的方法是，把當前節點的下一個節點的值，復制到當前節點上，然后再將當前節點連接到它的下下個節點。從內存上看，它刪掉的是當前節點的下一個節點。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def deleteNode(self, node):""":type node: ListNode:rtype: void Do not return anything, modify node in-place instead."""node.val = node.next.valnode.next = node.next.next刪除鏈表中的節點（給了整個鏈表，保證不重復）
另一種要刪除的是其內存。前面那種復制的方法就不行了。這種題一般會給你整個鏈表的頭節點。考慮到我們可能會刪掉頭節點。我們會用創建一個連向頭節點的虛擬節點的方式來解。當你熟悉了這一技巧，往后的變體就都大同小異。無疑是改變了一下要刪除節點的條件。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution:def deleteNode(self, head: ListNode, val: int) -> ListNode:dummy = ListNode(float("inf"))dummy.next = headnode = dummywhile node.next and node.next.val != val:node = node.nextnode.next = node.next.nextreturn dummy.next刪除鏈表中的節點（給了整個鏈表，可能會重復）
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def removeElements(self, head: ListNode, val: int) -> ListNode:dummy = ListNode(float("inf"))dummy.next = headnode = dummywhile node.next:if node.next.val == val:node.next = node.next.nextelse:node = node.nextreturn dummy.next刪除鏈表的倒數第N個節點
這題結合了之前的雙指針找倒數第K個節點的思路，先讓快指針先走 n+1 步，再一起走到結尾，則慢指針剛好位于倒數第 n+1 個節點。這時執行刪除操作。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:dummy = ListNode(0)dummy.next = headfirst, second = dummy, dummyfor i in range(n+1):first = first.nextwhile first:first = first.nextsecond = second.nextsecond.next = second.next.nextreturn dummy.next這往后的變體還可以是：刪除鏈表 N 到 M個節點。刪除鏈表第M個節點后的 N 個節點。等等。方法都大同小異。用雙指針找位置，用 dummy 虛擬節點避免刪除頭。
刪除重復節點 I
你可以看到，這段代碼和上面代碼唯一的區別就是判定條件那里改動了一下。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def deleteDuplicates(self, head: ListNode) -> ListNode:dummy = ListNode(float("inf"))dummy.next = headnode = dummywhile node.next:if node.val == node.next.val:node.next = node.next.nextelse:node = node.nextreturn dummy.next刪除重復節點 Ⅱ (不包含重復節點)
當我們要把重復節點全部去掉時，需要額外一個指針 pre 來作為輔助。如果存在兩個值相同的節點，當前指針 curr 就會一直往后走，直到跑到一個與該值不同的節點位置。讓pre .next = cur 完成節點的刪除。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def deleteDuplicates(self, head: ListNode) -> ListNode:dummy = ListNode(float('inf'))dummy.next = headcur = dummywhile cur:pre = curcur = cur.nextwhile cur and cur.next and cur.val == cur.next.val:val = cur.valwhile cur and cur.val == val:cur = cur.nextpre.next = curreturn dummy.next- 刪除重復節點 Ⅲ (未排序鏈表)
鏈表單調遞增時，能保證前面操作了某個值的刪除后，后面不會再操作與之一樣的刪除。但單調性不能保證時，原來的思路就不能照搬了。這時有兩種做法。一種是用哈希表，儲存重復過的數值。時間和空間復雜的都為 O(n)。另一種是兩遍循環操作，時間復雜度為 O(n2)，空間復雜度為 O(1)
class Solution:def removeDuplicateNodes(self, head: ListNode) -> ListNode:if not head:return headoccurred = set()occurred.add(head.val)pre = headwhile pre.next:cur = pre.nextif cur.val not in occurred:occurred.add(cur.val)pre = pre.nextelse:pre.next = pre.next.nextreturn headclass Solution { public:ListNode* removeDuplicateNodes(ListNode* head) {ListNode* p1 = head;while (node) {ListNode* p2 = p1 ;while (p2->next) {if (p2->next->val == p1->val) {p2->next = p2->next->next;} else {p2 = p2->next;}}p1= p1->next;}return head;} };從鏈表中刪去總和值為零的連續節點
這道題我們可以用前綴數組來解。第一遍遍歷時，我們用一個字典儲存前 k 個節點和 - 第k個節點的 pair。第二遍遍歷時，我們把當前節點的下一個都賦值為前綴字典中最后儲存的節點。
舉個例子說：
head = [1,2,-3,3,1]
前綴字典每次變化：
sum 操作
0 {0: dummy}
1 {0: dummy, 1: node[0]}
3 {0: dummy, 1: node[0], 3: node[1]}
0 {0: node[2], 1: node[0], 3: node[1]}
3 {0: node[2], 1: node[0], 3: node[3]}
4 {0: node[2], 1: node[0], 3: node[3], 4: node[4]}
第二次遍歷，鏈表變化：
sum 操作
0 dummy -> node[3]
1 node[0]-> node[1]
3 node[1] -> node[4]
0 node[2] -> node[3]
3 node[3] -> node[4]
4 node[4] -> None
匯總后，最終虛擬節點之后接的為：
dummy -> node[3] -> node[4] -> None
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def removeZeroSumSublists(self, head: ListNode) -> ListNode:hash_map = dict()dummy = ListNode(0)dummy.next = headnode = dummycurr_sum = 0while node:curr_sum += node.valhash_map[curr_sum] = nodenode = node.nextnode = dummycurr_sum = 0while node:curr_sum += node.valnode.next = hash_map[curr_sum].nextnode = node.nextreturn dummy.next3. 節點的求和 （全 4 道題）
這里主要用的是節點直接位置和值的關系。
- 二進制鏈表轉整數
直接每進一位，把之前的結果乘上2，再加上當前節點的值便可
class Solution:def getDecimalValue(self, head: ListNode) -> int:res = 0node = headwhile node:res = res*2 + node.val;node = node.nextreturn res兩數相加
該題與我們小學學加法豎式計算是一樣的。從低位到高位，用一個中間變量存進位。
Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:dummy = ListNode(0)p1, p2, cur = l1, l2, dummyoverflow = 0while p1 or p2:x = p1.val if p1 else 0y = p2.val if p2 else 0curr_sum = overflow + x + yoverflow = curr_sum // 10cur.next = ListNode( curr_sum % 10)cur = cur.nextif p1:p1 = p1.nextif p2:p2 = p2.nextif overflow > 0:cur.next = ListNode(overflow)return dummy.next兩數相加 II
如果我們要反過來相加，則需要借助棧這個數據結構。
class Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:s1, s2 = [], []while l1:s1.append(l1.val)l1 = l1.nextwhile l2:s2.append(l2.val)l2 = l2.nextres = Noneoverflow = 0while s1 or s2 or overflow != 0:p1_val = 0 if not s1 else s1.pop()p2_val = 0 if not s2 else s2.pop()curr_sum = p1_val + p2_val + overflowoverflow = curr_sum // 10curr_sum %= 10cur = ListNode(curr_sum)cur.next = resres = curreturn res鏈表求和
上面一題如果不使用額外空間要怎么做呢？方式是，我們用其中一個鏈表作為臨時變量存我們當前位的臨時結果。
class Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:dummy = ListNode(-1)cur = dummyoverflow = 0while l1 and l2:curr_sum = l1.val + l2.val + overflowl1.val = curr_sum % 10overflow = curr_sum // 10cur.next = l1cur = cur.nextl1, l2 = l1.next, l2.nextleft = Noneif l1:left=l1else:left=l2while left and overflow >= 0:curr_sum = left.val + overflowleft.val = curr_sum % 10overflow = curr_sum // 10cur.next = leftcur = cur.nextleft = left.nextif overflow > 0:cur.next = ListNode(overflow)return dummy.next4. 節點的位置調整 （全 11 題）
這類題目通常需要我們用多個指針，根據題目條件，控制某個節點前中后三個位置的轉換。
- 反轉鏈表
該題也有遞歸的解法：
class Solution(object):def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""if not head or not head.next:return headcur = self.reverseList(head.next)head.next.next = headhead.next = Nonereturn cur- 反轉鏈表 II （指定m到n反轉）
比上題多兩個步驟，一個是先走m-1步，找到要反轉的鏈表部分的起點的前一個節點A，另一個是用上述算法反轉 n-m 次后，讓A的下一個連到反轉后的鏈表，反轉后的鏈表的頭連到第n個節點。
class Solution:def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:dummy = ListNode(0)dummy.next = headA = dummyfor i in range(m-1):A = A.nextprev = Nonecurr = A.nextB = A.nextfor i in range(n-m+1):next_ = curr.nextcurr.next = prevprev = currcurr = next_A.next = prevB.next = next_return dummy.next遞歸法
class Solution(object):def reverseBetween(self, head, m, n):""":type head: ListNode:type m: int:type n: int:rtype: ListNode"""def reverseN(head,n):if n == 1:return head# 以 head.next 為起點，需要反轉前 n - 1 個節點last = reverseN(head.next, n-1)successor = head.next.next # 以head.next為開頭的鏈表已經完成翻轉，那么head.next.next正確指向后繼節點head.next.next = headhead.next = successorreturn lastif m == 1: return reverseN(head,n)head.next = self.reverseBetween(head.next,m-1,n-1)return head- 回文鏈表
當你熟悉了如何翻轉鏈表，你還可以用它來檢查回文。首先，我們用快慢指針的方式找到中點。然后對中點往后部分翻轉鏈表。再看看翻轉的后半部分和前半部分是否相等。
class兩兩交換鏈表中的節點
交換兩個節點的技巧之前在反轉鏈表中寫過。這里可以照用。不同在我們每次反轉局部的兩個節點后，往后要把 prev 移動到當前的第一個節點上。
class Solution:def swapPairs(self, head: ListNode) -> ListNode:if not head or not head.next:return headdummy = ListNode(0)dummy.next = headprev = dummywhile prev.next and prev.next.next:first = prev.nextsecond = prev.next.nextprev.next = secondfirst.next = second.nextsecond.next = firstprev = firstreturn dummy.next奇偶鏈表
class Solution:def oddEvenList(self, head: ListNode) -> ListNode:if not head:return headodd, even = head, head.nextoddHead, evenHead = odd, evenwhile even and even.next:odd.next = even.nextodd = odd.nexteven.next = odd.nexteven = even.nextodd.next = evenHeadreturn oddHead旋轉鏈表
這道題我們可以用返回倒數第k個節點的雙指針方法找到旋轉鏈表的新頭，然后將結尾給連上舊頭，讓新頭與前面的節點斷開，返回新頭，就完成了旋轉。
class Solution:def rotateRight(self, head: 'ListNode', k: 'int') -> 'ListNode':if not head or not head.next:return headnode = headn = 0while node:node = node.nextn += 1k = k % nif not k:return headfast, slow = head, headfor _ in range(k-1):fast = fast.nextslow_prev = Nonewhile fast.next:slow_prev = slowslow = slow.nextfast = fast.nextfast.next = headslow_prev.next = Nonereturn slow排序鏈表
比起 array 版本，不同的是我們要用 next 來做 i++ 的位移操作。空節點或單節點作為遞歸條件返回。一開始創建三個空節點，left，mid，right，并用對應的新指針 left_tail, mid_tail, right_tail 分別指向它們。接著我們遍歷鏈表，對于當前節點值比頭節點小的，就放在 left_tail 后面，若等于，就放在 mid_tail 后面，若小于，則放在 right_tail 后面。每次插入完，要后移其坐標。遍歷完后我們把結尾都歸 None。然后開始遞歸調用快排。把mid部分的快排結果放在鏈表 left 的右邊，把 right 的快排結果，放在鏈表 mid 的右邊。最后返回的是虛擬節點 left 右邊的節點，為最終排序好的整個鏈表。代碼如下：
class Solution:def get_tail(self, head):while head.next: head = head.nextreturn headdef sortList(self, head: ListNode) -> ListNode:if not head or not head.next:return headleft, mid, right = ListNode(-1), ListNode(-1), ListNode(-1)left_tail, mid_tail, right_tail = left, mid, rightval = head.valp = headwhile p:if p.val < val:left_tail.next = pleft_tail = left_tail.nextelif p.val == val:mid_tail.next = pmid_tail = mid_tail.nextelse:right_tail.next = pright_tail = right_tail.nextp = p.nextleft_tail.next = mid_tail.next = right_tail.next = Noneleft.next = self.sortList(left.next)right.next = self.sortList(right.next)self.get_tail(left).next = mid.nextself.get_tail(mid.next).next = right.nextres = left.nextreturn res從尾到頭打印鏈表
使用棧，先把遍歷鏈表把節點值放進棧，再一個個出棧。
class Solution:def reversePrint(self, head: ListNode) -> List[int]:stk = []node = headwhile node:stk.append(node.val)node = node.nextres = []while stk:res.append(stk.pop())return res重排鏈表
這道可以結合之前題的技巧，把問題分解成三步。第一步，用雙指針方法找到中點節點。第二步，用反轉鏈表方法把后半段反轉。第三步，合并兩個鏈表。
class Solution:def reverseList(self, head: ListNode) -> ListNode:prev = Nonecurr = headwhile curr:next_ = curr.nextcurr.next = prevprev = currcurr = next_return prevdef reorderList(self, head: ListNode) -> None:"""Do not return anything, modify head in-place instead."""if not head or not head.next:return head# 找中點slow, fast = head, headslow_prev = Nonewhile fast and fast.next:fast = fast.next.nextslow_prev = slowslow = slow.next# 中點后面的部分，翻轉鏈表slow_prev.next = Nonereversed_right = self.reverseList(slow)# 合并兩個鏈表first, second = head, reversed_rightwhile first and second:first_next, second_next = first.next, second.nextfirst.next, second.next = second, first_nextif not first_next and second_next:second.next = second_nextbreakfirst, second = first_next, second_nextreturn head對鏈表進行插入排序
如動圖所示，每次取出一個節點 curr，去和最開始的節點，往后一個個比較，如果發現它小于當前節點，就繼續右移，直到它大于等于當前節點，則執行插入操作。
class Solution:def insertionSortList(self, head: ListNode) -> ListNode:if not head or not head.next:return headdummy = ListNode(float("-inf"))dummy.next = headprev = dummycurr = dummy.nextwhile curr:if curr.val < prev.val:tmp = dummywhile tmp.next.val < curr.val:tmp = tmp.nextprev.next = curr.nextcurr.next = tmp.nexttmp.next = currcurr = prev.nextelse:prev, curr = prev.next, curr.nextreturn dummy.nextK 個一組翻轉鏈表
這道題的難點是需要常數空間。我們可以先寫好一個反轉鏈表。然后用三個指針 lastHead, currHead, nextHead 來分別表示要反轉鏈表的上一個尾節點，頭節點以及下一個要反轉的鏈表的頭節點。迭代時，部分反轉鏈表，再補連上。
class Solution:def reverse(self, head):prev = Nonecurr = headwhile curr:next_ = curr.nextcurr.next = prevprev = currcurr = next_return prevdef reverseKGroup(self, head: ListNode, k: int) -> ListNode:dummy = ListNode(0)dummy.next = headnode = dummylast_head = dummycurr_head = node.nextto_end = Falsewhile node:for _ in range(k):node = node.nextif not node:to_end = Truebreakif to_end:breaknext_head = node.nextnode.next = Nonereversed_head = self.reverse(curr_head)last_head.next = reversed_headlast_head = curr_headcurr_head.next = next_headnode = curr_headcurr_head = next_headreturn dummy.next5. 鏈表的分割 （全 2 道題）
分隔鏈表
左右兩邊各設置一個虛擬指針，一個用來接小于x的數，一個用來接大于等于x的數，最后再把兩段接起來，返回。
class Solution:def partition(self, head: ListNode, x: int) -> ListNode:dummy_left, dummy_right = ListNode(float("-inf")), ListNode(float("inf"))left, right = dummy_left, dummy_rightcurr = headwhile curr:if curr.val < x:left.next = currleft = left.nextelse:right.next = currright = right.nextcurr = curr.nextleft.next = dummy_right.nextright.next = Nonereturn dummy_left.next分隔鏈表
這道題就有點偏技巧性，需要先用余數預估長的有多少段，短的有多少段。
class Solution:def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:n = 0node = rootwhile node:n += 1node = node.nextnode = rootout = []remain = n % kshort_size = n // k long_size = short_size + 1for i in range(k):out.append(node)if remain > 0:size = long_sizeelse:size = short_sizenext_head = nodetail = Nonefor _ in range(size):tail = next_headnext_head = next_head.nextif tail:tail.next = Nonenode = next_headremain -= 1return out6. 鏈表的合并 （全 2 道）
兩個有序鏈表合并，看代碼比較簡單。需要用到虛擬節點 dummy 的技巧。
- 合并兩個有序鏈表
- 合并K個排序鏈表
這其實就是搜索引擎中的 MERGE 算法的變體。倒排索引中，每一個詞項會對應一個包含該詞項的文章ID，是一個長長的鏈表。我們如何把匹配到超過2個以上關鍵詞的篇章合并？實際會用到跳表去優化。但這道題相對簡單，只需要輸出合并后的排序序列便可。
核心思想和合并2個排序鏈表一致，但不同在我們需要維持一個最大容量為k的 buffer 來存放當前的中間節點值。我們可以用一個 heap 用來對 buffer 中的節點進行排序。每次出一個值最小的節點，放在要合并的鏈表的后面。時間復雜度為 O(nlogk)，空間復雜度為 O(k)
class7. 鏈表的復制 （就 1 道）
- 復雜鏈表的復制，復制帶隨機指針的鏈表
劍指 Offer 經典題目。先每個一個節點插入一個 node，然后利用 節點的下一個節點的隨機節點等于節點的隨機節點的下一個節點特性，來完成中間插入 node 的隨機節點連接的復制。最后再兩兩拆分便復制完成。
""" # Definition for a Node. class Node:def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):self.val = int(x)self.next = nextself.random = random """ class Solution:def copyRandomList(self, head: 'Node') -> 'Node':if not head:return headp = headwhile p:node = Node(p.val)next_ = p.nextp.next, node.next = node, next_p = next_p = headwhile p:if p.random:p.next.random = p.random.nextp = p.next.nextdummy = Node(0)dummy.next = headp1, p2 = dummy, head while p1 and p2:p1.next =p2.nextp1 = p1.nextp2.next = p1.nextp2 = p2.nextreturn dummy.next8. 與其它數據結構交叉 （全部 5 道）
- 二叉樹中的列表 （與二叉樹的 subTree 一樣）
解法上，我們需要些一個dfs，一旦存在當前鏈表節點和樹節點的值不匹配，就返回 False。否則，繼續往下遍歷找節點。時間復雜度
，空間復雜度為函數棧的調用，檢查鏈表長度不會超過樹的高度，因為超過就會返回 False，所以是 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def isSubPath(self, head: ListNode, root: TreeNode) -> bool:if not root:return Falseif not head:return Truedef dfs(head, root):if not head:return Trueif not root:return Falseif root.val != head.val:return Falsereturn dfs(head.next, root.left) or dfs(head.next, root.right)return dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)- 有序鏈表轉換二叉搜索樹 （與二叉樹相關）
思路是用中序遍歷是順序的。構建二叉樹時，用中序遍歷，每次節點就剛剛好與生成的樹對齊。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def sortedListToBST(self, head):""":type head: ListNode:rtype: TreeNode"""node = headn = 0while node:node = node.nextn += 1def dfs(l, r):nonlocal headif l >= r:return Nonemid = (l + r) // 2left = dfs(l, mid)root = TreeNode(head.val)root.left = left head = head.nextroot.right = dfs(mid+1, r)return rootreturn dfs(0, n)- 扁平化多級雙向鏈表 （與 bfs，dfs 相關）
- 鏈表組件 （使用 Set 作為去重技巧）
- 鏈表中的下一個更大節點 （鏈表與單調棧）
總結：一共 45 道題，刷了大概一周時間。一些常用的技巧不好用語言去總結，而是更多看代碼、自己去寫才會明白。大部分鏈表的基本思路就是虛擬節點，雙指針。其中雙指針用的最靈活。掌握了這幾個技巧，會發現很多題都是可以分解成幾個基本題的原型去做。另外鏈表與其它數據結構的綜合題，涉及的都是其它知識。日后會再一一總結。但愿在正式秋招之前能總結完頭部的專題。
最后附上這一專題的腦圖：
總結
以上是生活随笔為你收集整理的写出一段代码将链表中的两个节点位置互换位置_面试 leetcode 算法专题系列（二）—— 链表...的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Matplotlib - 柱状图、直方图
- 下一篇： 灰色关联分析_灰色关联分析模型研究综述