從LeetCode學演算法 - 12 Linked List (3)/ Stack (1)

0092. Reverse Linked List II (Medium)

Question

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

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

Example:

1
2
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中，要知道某個位置的節點為何，唯有從頭一路走到該節點 。
我們想要反轉的是mn的位置：
以範例來說，會將24的位置進行反轉。
如何反轉呢？首先我們要先走到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，兩者再和中間的節點連結起來，就完成整個反轉的流程。

重新整理解題的順序：

判斷m是否和n相等，相等則直接回傳原先的head。
定義一個迭代用節點node，先走到m-1的位置以取得節點left。
讓node從m一路走到n，將每個node放入到Stack中。
(註:放入的術語在堆疊中叫作push)
node再額外走一步會走到n+1的位置
依次將Stack中的節點取出，並且依序連接所有節點的next，
直到Stack中再也沒有節點。
(註:取出的術語在堆疊中叫做pop)
將反轉完的尾巴和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的宣告方式是：

1
Stack<> st = new Stack<>();

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

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

Java

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

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N), O(n-m)，因為我們的堆疊最多只需要存中間的部分和兩旁的node)

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

1
2
3
4
third = cur.next
cur.next = prev
prev = cur
cur = third

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

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