思想

鏈表的數(shù)據(jù)結構基礎是用額外的空間存儲下一個數(shù)據(jù)的位置，以此換取不連續(xù)內存的存儲，進而更高效的使用資源。
同時，鏈表在增刪方面的時間復雜度是 O(1)。
在處理鏈表相關的問題時，解題重點是搞清楚關系的處理，當前節(jié)點和后續(xù)節(jié)點的關系，和之前節(jié)點的關系。在此基礎上，往往使用遞歸的方式能夠快速的解題。

實例

反轉鏈表 leetcode 206

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

輸入：
ListNode，一個鏈表頭結點

輸出：
ListNode，反轉后的鏈表的頭結點

舉例：
當輸入是 [1,2,3,4,5] 的鏈表時，返回 [5,4,3,2,1] 的鏈表。

遞歸

遞歸的思路是思考反復執(zhí)行的重復過程，并找到 base case。
上例 [1,2,3,4,5]

1 -> 2 -> 3 -> 4 -> 5 -> None

頭結點開始反轉，后續(xù)通過遞歸完成。

1 -> reverse[null <- 2 <- 3 <- 4 <- 5]

reverse 是遞歸的部分，返回的結果如上描述，且返回了遞歸部分的頭結點 5。
這時 1.next 指向的是 2，接下來的遞歸操作應該是

1.next.next = 1

將 2 的下一個節(jié)點指向 1，完成 reverse

1.next = None

將 1 的下一個節(jié)點指向空
由此完成了遞歸的主體代碼，接下來描述 base case，當前節(jié)點為空或者下一個節(jié)點為空時返回當前節(jié)點。

編碼

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverse_linked_list_recursive(head: ListNode) -> ListNode:
    # base 條件，遞歸的返回條件
    if head is None or head.next is None:
        return head
    # 獲得反轉鏈表的表頭節(jié)點
    last = reverse_linked_list_recursive(head.next)
    # 遞歸主體
    head.next.next = head
    head.next = None
    return last


def reverse_linked_list_iterative(head: ListNode) -> ListNode:
    # 迭代初始設置，pre 設置成最后的 None，cur 指向當前 head
    pre, cur = None, head
    # 逐步迭代，每一次處理 pre, cur 和 cur.next 的關系
    while cur is not None:
        temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    return pre