引言
線性表（三）——線性表（六）這四節筆者介紹了鏈表的實作及變形，本節將簡單介紹幾種鏈表的應用，
反轉鏈表
問題來源：
力扣：206. 反轉鏈表
問題簡述：
給定一個鏈表，請將這個鏈表反轉，
問題分析：
在順序表中，我們常采用的反轉手段是根據索引交換串列的前半段和后半段實作反轉，但鏈表的存盤方式不同于順序存盤，那么我們該如何做呢？
一般而言，方法主要有兩種：
- 迭代式
- 設定當前游標cur，前驅節點pre
- 當cur非None時回圈，臨時存盤cur的下一個節點，然后將下一個節點修改為pre
- 將pre賦值為cur，此時cur的下一個節點為之前的pre
- 游標后移，直到迭代結束，回傳pre
- 遞回式
- 如果鏈表僅有一個元素，直接回傳
- 遞回到倒數第二個節點開始反向操作，head.next.next = head實作鏈表反轉，head.next = None斷開與后繼節點的鏈接防止形成環
- 遞回結束，回傳
Python實作：
# 迭代式
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head:
return
pre = None
cur = head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
# 遞回式
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
nextNode = self.reverseList(head.next)
head.next.next = head
head.next = None
return nextNode
模擬豎式計算
問題來源：
力扣：2. 兩數相加
問題簡述：
將兩個數分別逆序存盤在兩個鏈表中，請以鏈表的形式回傳這兩個數的和，
問題分析：
實作這一操作并不難，但有幾個細節需要注意：
- 十進制計算需要保存進位數
- 如果末尾進1(逆序)需要擴展鏈表，所以回圈時要判斷進位數是否為0
- 需要新建一個鏈表以方便處理頭部節點
Python實作：
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
res = ListNode(0)
cur = res # 游標
carry = 0 # 進位數
while l1 or l2 or carry:
residual1 = l1.val if l1 else 0
residual2 = l2.val if l2 else 0
cur.next = ListNode((residual1+residual2+carry) % 10)
carry = (residual1 + residual2 + carry) // 10
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
cur = cur.next
return res.next
尋找環起點
問題來源：
力扣：142. 環形鏈表
問題簡述：
給定一個鏈表，判斷是否存在環，若存在，找出環起點，
問題簡述：
筆者在第一次碰到這個問題的時候想法是直接使用哈希表記錄經過的結點，第一次碰到的重復的結點一定是環起點，但這樣做的壞處是無法在O(1)空間下解決這一問題，
仔細思考，我們會發現通過快慢指標可以優化空間，利用快慢指標可以迅速判環，如果存在換且快慢指標第一次相遇，通過數學推導會發現此時慢指標與環起點的距離同鏈表起點與環起點的距離“相同”，因此再設定第三個指標與慢指標同向移動即可到達環起點，
Python實作：
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
# 判環
cur1, cur2 = head, head
while cur2 and cur2.next:
cur1 = cur1.next
cur2 = cur2.next.next
if cur1 == cur2:
break
if cur2 is None or cur2.next is None:
return
# 快指標走的路是慢指標的兩倍，它們走的非環路相同，且慢指標在繞環第一圈必定與快指標相遇
# 設非環路為s，環起點至相遇點為x，相遇點至環起點為y，快指標繞圈數為n
# 公式2*(s+x) = s + x + n*(x+y) ==> s = y + (n-1)*(x+y)
# 推導公式后一部分為環的整數倍，因此不影響計算，可以得知當第一次相遇時慢指標距離環口s步
# 設定一個新指標指向鏈表起點，與慢指標同向同速移動，移動y + (n-1)*(x+y)步必定相遇于環口
# 尋找環起點
cur3 = head
while cur3 != cur1:
cur1 = cur1.next
cur3 = cur3.next
return cur1
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/169432.html
標籤：其他
上一篇：Excel檔案匯入匯出操作