iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 13
2
Software Development

從LeetCode學演算法系列 第 13

[Day 13] 從LeetCode學演算法 - 0092. Reverse Linked List II (Medium)

目標:
這題主要目的在於理解常見的資料結構:堆疊(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)


上一篇
[Day 12] 從LeetCode學演算法 - 0089. Gray Code (Medium)
下一篇
[Day 14] 從LeetCode學演算法 - 0100. Same Tree (Easy)
系列文
從LeetCode學演算法30

尚未有邦友留言

立即登入留言