0092. Reverse Linked List II - chasel2361/leetcode GitHub Wiki

Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.

Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

這個題目的重點在於如何將單向串接的串列在指定的位置反向連接，我自己試了一下，主要概念是把需要轉向的部分用一個 list 存起來，需要的時候再拿出來用。有寫出符合例題的狀況，但如果把 m, n 改掉就會失敗，所以決定參考雨蕭大大的寫法。

他的想法跟我類似，但又更精細一點，除了利用 stack: [list] 把需要轉向部分存起來之外，還多了一個 left 值儲存 m 的前一個位置，以方便後續連接。

stack 這種資料結構的特性是後進先出，在 python 中可以用 list 的形式實現，輸入時使用 list.append() ；提出時使用 list.pop()。

反轉的部分可以使用 list.pop() 的函式，它會自動取出最後一個值並刪除。但這只有解決取出順序的問題，反向串接需要使用兩個變數，先令 l1 = stack.pop(), l2 = None，再進入迴圈，裡面先把 l2 指向 stack.pop()，接著把 l1.next 指向 l2 得到第一個反向連接、再把 l1 指向 l2 清出一個下一個 stack.pop() 的空間 ( 每次 l1 所在的位置，都是當前準備進行連接 next 的節點 ) ，直到 stack 不存在為止，便完成反向連接。

另外還需要考慮 m = 1 的狀況，此時需要將 head 指向 l1 ，也就是第一個開始反向連接的節點

由此可以得出以下程式碼：

[1] 若 m = n 就不需要反轉，直接回傳 head
[2] 當 node 移動到 m, n 之間時，使用 stack 來儲存這些需要反轉的節點
[3] 當 m = 1 時，需要將 head 指向 l1 ，變更起始節點
[4] 當 m != 1 時，將 l1 接到 left.next
[5] 反向連接結束後，需要接回 node ，結束動作

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if m == n: return head  # [1]
            
        stack = []
        left, node = None, head
            
        if m != 1:
            for _ in range(1, m - 1):
                node = node.next
            left = node
            node = node.next
            
        for _ in range(m, n + 1):
            stack.append(node)  # [2]
            node = node.next
            
        l1, l2 = stack.pop(), None
        if m == 1:
            head = l1  # [3]
        else:
            left.next = l1  # [4]
        
        while stack:
            l2 = stack.pop()
            l1.next = l2
            l1 = l2
        l1.next = node  # [5]
        return head

這樣寫的時間複雜度是 O(N)，空間複雜度是 O(N)

Code Link