@Author：Runsen

@Date：2020/9/13

鏈表是我這輩子的痛啊，每次學到鏈表，就往往不會，就沒有繼續學下去。現在大四不能繼續讓這個鏈表阻礙我了。現在基本是重刷數據結構和算法，畢竟筆試真的太重要了。 我又重溫了爭大佬專欄的棧，又鞏固了下。

爭哥專欄有一個非常的經典：就是關于指針的理解：將某個變量賦值給指針，實際上就是將這個變量的地址賦值給指針，或者反過來說，指針中存儲了這個變量的內存地址，指向了這個變量，通過指針就能找到這個變量。

涉及到鏈表的操作，重新看了專欄，一定要在紙上把過程先畫出來，再寫程序。對于鏈表其實基本就是單鏈表，很少是雙鏈表，或者循環鏈表的題目

由于一個節點只通過next指針保存了它的下一個節點，失去了它的前驅節點信息，而且單鏈表數據結構通常長度未知，因此幾乎所有單鏈表題目都是在前驅節點和長度上做文章。
常見鏈表面試算法，可以使用雙指針迭代的方式以及遞歸的方式。

下面就是我2020/9/13 在leetcode 刷的鏈表題目，很多注釋都寫清楚了。關于題目的描述，這里不直接抄Leetcode 了。

文章目錄

• LeetCode206 反轉一個單鏈表
• Leetcode 第二題 addTwoNumbers
• 劍指 Offer 18. 刪除鏈表的節點
• 面試題 02.03刪除中間節點
• 面試題 02.01. 移除重復節點
• 面試題 02.06 回文鏈表
• Leetcode 143. 重排鏈表
• 劍指 Offer 22. 鏈表中倒數第k個節點
• Leetcode19. 刪除鏈表的倒數第N個節點

LeetCode206 反轉一個單鏈表

這個反轉單鏈表，寫了N次，但又寫的時候，又寫不出來。服了，自己。看似，簡單，博客最起碼寫了3次 反轉一個單鏈表

class Solution:def reverseList(self, head: ListNode) -> ListNode:prev = Nonecur = headwhile cur:# prev 指cur.next cur指prev cur.next指curcur.next,prev,cur = prev,cur,cur.nextreturn prev

Leetcode 第二題 addTwoNumbers

class Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:# 將l1鏈表的數取出，組成一個數，l2同理，最終求和，將求和結果循環得出每個節點的值，然后鏈表連接即可！！！# 將鏈表轉化列表val1, val2 = [l1.val], [l2.val]print(val1) #[2]print(val2) #[5]while l1.next:val1.append(l1.next.val)l1 = l1.nextwhile l2.next:val2.append(l2.next.val)l2 = l2.nextprint(val1) #[2, 4, 3]print(val2) #[5, 6, 4]# 反轉列表 用join方法拼接數字 切片[::-1]num_1 = ''.join([str(i) for i in val1[::-1]])num_2 = ''.join([str(i) for i in val2[::-1]])sums = str(int(num_1) + int(num_2))[::-1] # 708# 將sum轉化成鏈表res# 頭節點res = head = ListNode(int(sums[0]))for i in range(1, len(sums)):# 拼接head.next = ListNode(int(sums[i]))head = head.nextreturn res

劍指 Offer 18. 刪除鏈表的節點

class Solution:def deleteNode(self, head: ListNode, val: int) -> ListNode:# 如果頭結點為空，直接返回if not head:return head# 如果頭結點值等于val，直接返回head.next（題設中有注明鏈表中元素不重復）if head.val == val:return head.next# 定義一個指針cur = headwhile cur.next:# 關鍵步驟，如果next的值等于val，跳過該節點if cur.next.val == val:cur.next = cur.next.nextbreakcur = cur.nextreturn head

面試題 02.03刪除中間節點

# 將要刪除節點的 val 賦值為下一結點的 val node.val = node.next.val # 然后將要刪除節點的下一結點指向要刪除節點的下一結點的下一結點 node.next = node.next.next

面試題 02.01. 移除重復節點

class Solution:def removeDuplicateNodes(self, head: ListNode) -> ListNode:# 如果沒有head，那么直接returnif not head: return # 用集合來儲存起來visited = {head.val}cur = head# 處理當前節點的下一個節點while cur and cur.next:# 如果當前的val在字典中，那么直接不要 if cur.next.val in visited:cur.next = cur.next.nextelse:# 集合的add 直接加入 集合或者元組都可以visited.add(cur.next.val)# 往下遍歷cur = cur.nextreturn head

面試題 02.06 回文鏈表

class Solution:def isPalindrome(self, head: ListNode) -> bool:# 鏈表轉化為列表，判斷是不是 回文res = []cur = headwhile cur:res.append(cur.val)cur = cur.next# print(res)if res[::-1] == res:return Trueelse:return False

Leetcode 143. 重排鏈表

class Solution:'''@Author :Runsen給定鏈表 1->2->3->4, 重新排列為 1->4->2->3.給定鏈表 1->2->3->4->5, 重新排列為 1->5->2->4->3.就是每次取兩邊，先左到右 1 -> 2 -> 3 -> 4 -> 5 -> 6第一步，將鏈表平均分成兩半1 -> 2 -> 34 -> 5 -> 6第二步，將第二個鏈表逆序1 -> 2 -> 36 -> 5 -> 4第三步，依次連接兩個鏈表1 -> 6 -> 2 -> 5 -> 3 -> 41 -> 2 -> 3 -> 4 -> 5 -> 6'''# 思路 找到中間節點，然后將右面的翻轉，先定義一個翻轉函數，Leetcode 206題def reverseList(self, head):pre = Nonecur = headwhile cur:cur.next, pre, cur = pre, cur, cur.nextreturn predef reorderList(self, head: ListNode) -> None:"""Do not return anything, modify head in-place instead."""if not head:return headslow, fast = head, headwhile fast and fast.next:slow, fast = slow.next, fast.next.next# 尋找中間節點 快慢指針中的慢指針就是中間節點p = slow.nextslow.next = Nonep = self.reverseList(p)# 這個時候的p就是鏈表右面的翻轉m = headwhile p:# 怎么拼接？# m ,m.next, p, p.next => p, m.next, m.next, p.next 返回的是m這個鏈表m.next, p.next, m, p = p, m.next, m.next, p.next

劍指 Offer 22. 鏈表中倒數第k個節點

最常規的方法就是將鏈表變成數組，直接一個索引取值就可以了。

class Solution:def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:res = []while head:res.append(head)head = head.nextreturn res[-k]

有的大佬給出快慢指針的方法，就是快指針先走 K 步，然后再快慢指針一起走，當快指針跑出來時，慢指針的就是倒數第k個節點。

class Solution:def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:former, latter = head, headfor _ in range(k):former = former.nextwhile former:former, latter = former.next, latter.nextreturn latter

參考：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/solution/mian-shi-ti-22-lian-biao-zhong-dao-shu-di-kge-j-11/

Leetcode19. 刪除鏈表的倒數第N個節點

給定一個鏈表，刪除鏈表的倒數第 n 個節點，并且返回鏈表的頭結點。

示例：

給定一個鏈表: 1->2->3->4->5, 和 n = 2.

當刪除了倒數第二個節點后，鏈表變為 1->2->3->5.

這題和上面那題是一樣的，都是快慢指針，只不過這里需要返回鏈表的頭結點。那定義一個Node = ListNode(None)就可以了。

class Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:# 快慢指針Node = ListNode(None)Node.next = headfirst,slow = Node,Nodefor i in range(n):first = first.nextwhile first.next != None:first = first.nextslow = slow.nextslow.next = slow.next.nextreturn Node.next

不知不覺現在到了下午三點，從早上九點半到現在，刷了九題的鏈表算法題目，真心累！！！！

總結

以上是生活随笔為你收集整理的为了OFFER，花了几个小时，刷下Leetcode链表算法题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。