昨天我們掌握了如何反轉整個鏈結串列，今天我們挑戰「局部反轉」。

題目連結: 92. Reverse Linked List II

題目描述:給你一個單向鏈結串列的頭節點 head 和兩個整數 left、right，請你反轉從位置 left 到位置 right 的節點，並返回修改後的鏈結串列的頭節點。

Python

解題思路:

• 首先找到需要反轉區間的前一個節點 p0。
• 將反轉區間內的節點，一個個「抽」出來，插入到 p0 的後面，形成新的反轉頭部。

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(next = head)
        pre = None
        p0 = dummy
        for _ in range(left-1):
            p0=p0.next
        curr = p0.next
        for _ in range(right-left):
            temp = curr.next
            curr.next = temp.next
            temp.next = p0.next
            p0.next = temp
        return dummy.next

演算法分析:

• 創建虛擬節點dummy並連至head頭部，dummy.next 指向 1。p0 指向 dummy。
• for _ in range(left - 1):將p0移動至要反轉區間的前一節點。
• curr = p0.next讓curr當作反轉區間的第一個數字，curr指向節點 2。
• 接著for _ in range(right-left):裡面反轉的邏輯就跟昨天的題目是一樣的。

流程大概是如下:
初始時:
dummy -> 1 (p0) -> 2 (curr) -> 3 -> 4 -> 5

第一輪迴圈:
1 (p0) -> 3 -> 2 (curr) -> 4 -> 5

第二輪迴圈:
1 (p0) -> 4 -> 3 -> 2 (curr) -> 5

迴圈結束。

複雜度分析:

• 時間複雜度為 O(n)(我們需要遍歷 left-1 次找到 p0，然後再遍歷 right-left 次來進行反轉)。

• 空間複雜度： O(n)(我們只使用了 dummy, p0, curr, temp 等固定數量的額外指標。)。

這樣有清楚Linked List的操作了嘛!
有問題可以底下留言!
下回見!!