目標：
這題主要目的在於理解常見的資料結構：堆疊(Stack)，
同時也會處理常見的Linked List。

原題：

Question:
Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of the list.

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

分析/解題：
給定一個linked list，在只經過一次的操作下(每個node不會額外再走訪)，
題目要求將m到n的位置的節點進行反轉。

由範例可知這邊的m跟n是以開頭為1而非0來計算，這點讀者請特別留意。

我們先從理論上來看這題應該怎麼處理：
首先根據題目要求，m可能和n相等，
相等的狀況下其實完全不用做事，回傳head即可。

那麼如果是不相等的狀況呢？
在Linked List中，要知道某個位置的節點為何，唯有從頭一路走到該節點。
我們想要反轉的是m~n的位置：
以範例來說，會將2~4的位置進行反轉。
如何反轉呢？首先我們要先走到2的左邊，當我們把中間的部分反轉後，
我們還要將它們和左右兩邊接起來，要記得2的左邊跟4的右邊的節點才行。
(不然接不起來就GG了XD)
這邊將2的左邊命名為left，一路往下走的迭代節點命名為node，
走到m-1以前先記錄下left節點，再繼續往下走。

接下來問題來了，如何將2~4的部分反向連接呢？
你可以選擇一個一個拆解並重新鍵結，
但這裡筆者想介紹一個常用的資料結構：Stack(堆疊，或稱棧/堆棧)。
Stack的樣子，就跟某些苦命的辦公室人員的書桌一樣：
你會嘗試將書桌上的文件/工作處理完，但老闆總是會往上面再加新的。
也就是說，每次如果你選擇從最上面開始拿
(別從中間或下面，這麼高的文件可是會塌的！)，
你會拿到最新的工作。

Stack也是如此，假設你將1, 2, 3, 4, 5依序放入Stack中，
那麼當你從Stack裡面拿東西的時候，拿出來的順序會是5, 4, 3, 2, 1。
最後放進去的會最先被拿出來，
這樣子的特性我們稱之為Last In First Out(後進先出，簡寫為LIFO)。
有另一種資料結構叫Queue(隊列，或稱佇列)跟它剛好相反，是先進先出，
我們以後找機會再講解它。

如果這題應用上Stack的話，就簡單許多：
我們將2~4的部分通通丟進Stack中，再一個一個拿出來，
這時候順序就會變成4, 3, 2了！那麼，只要將剛剛存好的left，
以及後面我們邊走邊看到4的時候，將它的右邊記錄起來的node，
兩者再和中間的節點連結起來，就完成整個反轉的流程。

重新整理解題的順序：

1. 判斷m是否和n相等，相等則直接回傳原先的head。
2. 定義一個迭代用節點node，先走到m-1的位置以取得節點left。
3. 讓node從m一路走到n，將每個node放入到Stack中。
   (註:放入的術語在堆疊中叫作push)
4. node再額外走一步會走到n+1的位置
5. 依次將Stack中的節點取出，並且依序連接所有節點的next，
   直到Stack中再也沒有節點。
   (註:取出的術語在堆疊中叫做pop)
6. 將反轉完的尾巴和node做連接，結束整個反轉的流程。

這當中還有額外一點需要注意的是m=1的狀況，
因為我們最後回傳的是用head來代表整個linked list，
如果m為1的話，代表head其實已經被改變了，
我們需要同步更新head的部分。

請參照Java的寫法，我們採用了l1和l2兩個節點來處理依序連接的部分。
我們會先取出堆疊中第一個節點，這個節點會被left連接，
接下來使用l2 = st.pop(); l1.next=l2; l1 = l2;
來進行一次取一個node，將前後連接好以後，
將位置移到下一個準備連接的點。
也就是說，每次l1所在的位置，都是當前準備進行連接next的節點。
(若讀者對這邊的說明感到抽象，請務必在紙上試著操作一下會較清楚)

在Java中，Stack的宣告方式是：
Stack<> st = new Stack<>();

請在"<>"之中填入你想要使用的資料型態，
在本例中為題目已經定義的class ListNode。

函式用法的部分，push()用來放入節點，pop()用來取出節點，
isEmpty()則是檢查Stack是否是空的。
(還有一個peek()，是用來看Stack最上面節點，
但不會真的將節點從Stack中移除)

Java:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == n) return head;
        Stack<ListNode> st = new Stack<>();
        ListNode left = null;
        ListNode node = head;
        if (m != 1) {
            for (int i = 1; i < m - 1; ++i) node = node.next;
            left = node;
            node = node.next; // position m
        }
        
        for (int i = m; i <= n; ++i) {
            st.push(node);
            node = node.next;
        }
        
        ListNode l1 = st.pop(), l2 = null;
        if (m == 1)
            head = l1;
        else
            left.next = l1;
        while (!st.isEmpty()) {
            l2 = st.pop();
            l1.next = l2;
            l1 = l2;                
        }
        l1.next = node;
        
        return head;
    }
}

在Python中，list的特性可以方便的用來當作Stack使用，
放入節點可以使用append()，取出節點使用pop()。

Python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if m == n: return head
        st = []
        left, node = None, head
        if m != 1:
            for i in range(1, m - 1):
                node = node.next
            left = node
            node = node.next # position m
        
        for i in range(m, n + 1):
            st.append(node)
            node = node.next
        
        l1, l2 = st.pop(), None
        if m == 1:
            head = l1
        else:
            left.next = l1
        
        while st:
            l2 = st.pop()
            l1.next = l2
            l1 = l2
        
        l1.next = node
        
        return head

面試實際可能會遇到的問題：
「時間/空間複雜度？」
(O(N), O(n-m)，因為我們的堆疊最多只需要存中間的部分和兩旁的node)

「可以只用O(1)的空間嗎？」
(可以，如果我們按順序一個一個處理m~n之間的連結，
最後再將n和m和左右兩邊連起來，是可以不使用Stack的
中間的連接方式會像是：

third = cur.next
cur.next = prev
prev = cur
cur = third

讀者有興趣的話可以嘗試看看。)

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0100. Same Tree (Easy)