我已經遞回地看到了反向鏈接串列的解決方案，但我不理解 head.next.next 部分。誰可以給我解釋一下這個。這是 leetcode 206 問題。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
curr = self.reverseList(head.next)
head.next.next = head
head.next = None
return curr
當遞回函式到達末尾并將串列的最后一個值回傳給curr時，curr的next和head的next是None，對嗎？所以我覺得 head.next.next 應該會拋出錯誤。請向我解釋這個解決方案以及為什么它沒有錯。
uj5u.com熱心網友回復：
當遞回函式到達末尾并將串列的最后一個值回傳給
curr時，nextofcurr和nextofhead是 None 對嗎？
第一個說法是正確的。curr.next將是None，但第二個說法是不正確的。head沒有參與遞回呼叫。遞回呼叫將反轉緊隨其后 head的較短串列，但head節點本身被排除在該行程之外，因此遞回呼叫無法以某種方式修改head.next。
所以我覺得
head.next.next應該拋出一個錯誤。
它不會。函式頂部的基本案例測驗保證遞回呼叫僅在head.nextis not時進行None。而且由于遞回呼叫無法改變head.next（因為它沒有那個head參考），當遞回呼叫回傳時，這仍然是正確的。
使用 4 個節點的串列來可視化這一點可能會有所幫助。
head
↓
┌───────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 1 │ │ val: 2 │ │ val: 3 │ │ val: 4 │
│ next: ──────? │ next: ──────? │ next: ──────? │ next: None│
└───────────┘ └───────────┘ └───────────┘ └───────────┘
Nowself.reverseList(head.next)被呼叫，這意味著遞回呼叫不會“看到”第一個節點，而是它的后繼節點。該節點是具有 3 個節點的串列的開始。這個遞回呼叫有它自己的名稱head和curr名稱，我將用重音來區分（因為它們實際上是本地名稱）。在遞回執行開始時，我們有這個狀態：
head'
↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 2 │ │ val: 3 │ │ val: 4 │
│ next: ──────? │ next: ──────? │ next: None│
└───────────┘ └───────────┘ └───────────┘
讓我們假設這個串列是正確反轉的（我們可以通過所有步驟來證明這一點，但我將跳過該程序）。這意味著在此遞回呼叫結束時，將回傳對最后一個節點的next參考，并且這些節點中的參考已更新，如下所示：
head' curr'
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 2 │ │ val: 3 │ │ val: 4 │
│ next: None│ ?────── :next │ ?────── :next │
└───────────┘ └───────────┘ └───────────┘
遞回呼叫現在結束，并回傳對最后一個節點 ( curr') 的參考，呼叫者將該參考分配給它自己的curr名稱。這是呼叫者的狀態：
head curr
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 1 │ │ val: 2 │ │ val: 3 │ │ val: 4 │
│ next: ──────? │ next: None│ ?────── :next │ ?────── :next │
└───────────┘ └───────────┘ └───────────┘ └───────────┘
同樣，head它超出了遞回呼叫的范圍，因此沒有任何改變：它的next屬性保持原樣。
現在我們得到最后兩個分配，它們用于將第一個節點附加到反向子串列的末尾。反向子串列的尾部是 at head.next，并且head.next.next = head會給我們這個結果：
head curr
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 1 │┌? │ val: 2 │ │ val: 3 │ │ val: 4 │
│ next: ─────┘?────── :next │ ?────── :next │ ?────── :next │
└───────────┘ └───────────┘ └───────────┘ └───────────┘
最后，head.next設定為None，因為該節點已成為反向串列的尾部：
head curr
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ val: 1 │ │ val: 2 │ │ val: 3 │ │ val: 4 │
│ next: None│ ?────── :next │ ?────── :next │ ?────── :next │
└───────────┘ └───────────┘ └───────────┘ └───────────┘
希望這可以澄清它。
uj5u.com熱心網友回復：
遞回函式永遠不會到達串列中的最后一個值，因此不會引發錯誤。在遞回期間，該函式接受head.next指向的節點，而不是 head 本身。因此，停止條件實際上是檢查條件：（如果不是head.next或不是head.next.next）。
另一種看待它的方法是考慮當函式處理 n 長度串列的第 (n-1) 個節點時會發生什么。reverseList()函式將接收第 (n) 個節點 - 這里head.next將為None，程式將回傳head并因此停止遞回。
uj5u.com熱心網友回復：
您應該嘗試使用非常短的輸入（例如ListNode(1, ListNode(2)).
有了這個輸入，頂層函式就很容易理解了。head參考是對節點的參考1，并且head.next是該節點中對2節點的參考。我們可以這樣畫：
head->1->2->None
head.next.next是 2 節點中對接下來出現的任何內容的參考，對于此輸入，它是None，因為它是串列的末尾。
當您分配 to 時head.next.next，您正在將該參考替換為對所None參考的同一節點head（即1節點）的參考，這會暫時在鏈表中產生一個小回圈：
head->1->2
^ \
\__/
但是，當我們執行下一步時，我們洗掉了從1節點到節點的鏈接，這打破了回圈，只剩下從節點到節點的反向鏈接。如果我們重新排列一下，我們有：2head.next = None21
cur->2->1->None
^
/
head
如您所見，head在我們的代碼中仍然指向1節點，所以我們不想回傳它，因為它不在反向串列的開頭。相反，我們回傳cur，我們從遞回中得到的值，它總是來自原始鏈表的最后一個節點（2在這種情況下它是節點，但如果我們傳入一個更長的串列，它可能是幾個節點遠離我們的head東西head.next）。該節點是新反向串列的頭部。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/520642.html
標籤：Python递归链表