思想
鏈表的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)是用額外的空間存儲下一個數(shù)據(jù)的位置，以此換取不連續(xù)內(nèi)存的存儲，進而更高效的使用資源。
同時，鏈表在增刪方面的時間復雜度是 O(1)。
在處理鏈表相關(guān)的問題時，解題重點是搞清楚關(guān)系的處理，當前節(jié)點和后續(xù)節(jié)點的關(guān)系，和之前節(jié)點的關(guān)系。在此基礎(chǔ)上，往往使用遞歸的方式能夠快速的解題。
實例
反轉(zhuǎn)鏈表的一部分 leetcode 92
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
輸入：
（1）head: ListNode，一個鏈表頭結(jié)點；
（2）left: int，反轉(zhuǎn)起始位置；
（3）right: int，反轉(zhuǎn)結(jié)束位置。
輸出：
ListNode，部分反轉(zhuǎn)后的鏈表的頭結(jié)點
舉例：
當輸入 head = [1,2,3,4,5]，left = 2，right = 4 時，反轉(zhuǎn)鏈表 2 到 4 位置的元素，返回 [1,4,3,2,5]。
遞歸
遞歸的思路是思考反復執(zhí)行的重復過程，并找到 base case。
任意部分的鏈表反轉(zhuǎn)比較復雜，需要處理開頭和結(jié)尾兩個位置。先簡化問題，處理反轉(zhuǎn)前 N 個元素的鏈表反轉(zhuǎn)問題：
上例先簡化為 head = [2,3,4,5], n = 3，反轉(zhuǎn)前三個鏈表元素，返回 [4,3,2,5]
2 -> 3 -> 4 -> 5 -> None
這個問題要識別當前元素的位置，因為只有前 n 個反轉(zhuǎn)，后續(xù)不動。
2 -> reverse[null <- 3 <- 4] -> 5
reverse 是遞歸的部分，返回的結(jié)果如上描述，且返回了遞歸部分的頭結(jié)點 4。
這時 2.next 指向的是 3，接下來的遞歸操作應該是
2.next.next = 2
將 2 的下一個節(jié)點指向 5，完成 reverse
2.next = 5
由此完成了遞歸的主體代碼，接下來描述 base case 并要識別后續(xù)不需要反轉(zhuǎn)的頭結(jié)點。
if n == 1:
# 這個例子進入 base 條件時，節(jié)點在 4，此時的非反轉(zhuǎn)頭結(jié)點就是 5
successor = cur.next
reverse(head.next, n - 1)
當完成了簡化問題的處理后，加入頭部開始位置的遞歸判斷。
if left != 1:
# 如果當前節(jié)點不是反轉(zhuǎn)的起始位置，則進入下一個節(jié)點，形成子鏈，此時子鏈的反轉(zhuǎn)區(qū)間左右都減 1
head.next = reverse(head.next, left - 1, right - 1)
編碼
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
successor = None
def reverseN(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if n == 1:
self.successor = head.next
return head
last = self.reverseN(head.next, n - 1)
head.next.next = head
head.next = self.successor
return last
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
if left == 1:
return self.reverseN(head, right)
head.next = self.reverseBetween(head.next, left - 1, right - 1)
return head
