Linked List 的反轉操作 – 陪你刷題

在做 linked list 相關題目時,不論是 recursive 還是 iterative 寫法,寫起來都相當燒腦,因此決定以自己好理解的方式,整理一篇跟 linked list 反轉操作的文章,作為往後複習來用。

Leetcode #206 Reverse Linked List

遞迴寫法

在開始透過遞迴的方式來反轉 linked list 之前 ,先回想使用遞迴的定義,使用遞迴需要滿足以下3個條件:

  1. 一個問題的解可以分為幾個子問題的解
  2. 這個問題和其子問題除了數據規模不同,求解思路完全一樣
  3. 存在遞迴終止條件

在思考遞迴問題時,很重要的一點是,絕對不要在腦中想把遞迴一層一層的想清楚,這不符合一般人腦的思考方式!

單純聚焦於反轉過程中的某一子問題,可以幫助我們思考清楚整個遞迴,如下圖,如果反轉完 head→next ,接著該怎麼反轉 head 呢?

LinkedlistReverse

第一步將 head→next 接往 head 做到反轉:

head->next->next = head;

第二步將 head→next 指到 NULL ,至此 head 節點的前後都被正確反轉。

head->next = NULL;

遞迴問題中,必須定義出終止條件,以反轉 linked list 來說,當走到最後一個節點時後,該節點就不需要再往後處理,而這個節點就會是新的 head 節點,應該將新頭節點回傳。

掌握以上要點後,遞迴的程式碼也就可以輕鬆寫出。

ListNode *reverseList (ListNode *head)
{
    if (head->next == nullptr)
        return head;
    ListNode *new_head = reverseList (head->next);
    had->next->next = head;
    head->next = NULL;
    return new_head;
}

非遞迴寫法

  • 專注於當前節點的反轉即可。
  • 因為反轉操作而喪失連結的節點,需要儲存起來。
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr)
            return NULL;

        ListNode *prev = nullptr, *nxt; 
        while (head != nullptr)
        {
            nxt = head->next;
            head->next = prev;
            prev = head;
            head = nxt;
        }

        return prev;
    }
};

Leetcode #92 Reverse Linked List II

此題的 input 給你 [m, n] 的區間,要你 reverse 特定區間內的節點,以下分為遞迴與非遞迴的寫法。

遞迴寫法

我們先從如何 reverse 前 N 個節點開始了解。

Reverse 前 N 個節點

與 reverse 整個 linked list 差別在於:
1. 必須將反轉過後的 linked list 的尾節點 (圖中的 new_tail 或反轉前的 head ) 接往第 N+1 個節點 (圖中的 successor 或者你要說它是反轉區間最後節點的下一個節點),之前 reverse 整個 linked list 時候,會將當前的節點的 next 指向 NULL ,但這個 case 下要將當前節點指向第 N+1 的節點。

reverseN

遞迴的 base case 為當 n=1 的時候,代表不必再反轉後續節點,但是要將第 N+1 個節點紀錄下來,並且回傳新的頭節點。

ListNode *successor = nullptr;

ListNode *reverseN (ListNode* head, int n)
{
    if (n == 1)
    {
        successor = head->next;
        return head;
    }
    ListNode *new_head = reverseN (head->next, n-1);
    head->next->next = head;
    head->next = successor;
    return new_head;

}

反轉特定區間節點

知道如何 reverse 前 N 個節點後,其實 reverse 區間 [m, n] 的節點,等同於我們先前進到第 m 個節點,就以第 m 個節點開始來 reverse n-m 個節點即可。

透過遞迴來實作的話,遞迴的 base case 即為 m = 1 的時候,回傳反轉後的新頭節點,其他的 case 下直接將節點一個一個走下去,更新區間的開頭與結束 index 即可。

ListNode* reverseBetween (ListNode *head, int m, int n)
{
    if ( m == 1)
    {
        return reverseN (head->next, n);
    }
    head->next = reverseBetween (head->next, m-1, n-1);
    return head;
}

非遞迴寫法

相較於遞迴寫法更加複雜,以下圖為例,可以觀察到兩個現象:

  1. 反轉區間的前一個節點永遠接往新的頭節點(圖中的 new_head )
  2. 反轉過後的 linked list 的尾節點 (圖中的 new_tail )接往反轉區間的後一個節點

只要在每次反轉時把握兩個現象正確,再搭配反轉動作,就可以正確完成反轉區間的任務。總結一下,每次都反轉都會做到以下三樣任務:

  1. 反轉區間的前一個節點永遠接往新的頭節點(圖中的 new_head )
  2. 反轉過後的 linked list 的尾節點 (圖中的 new_tail )接往反轉區間的後一個節點
  3. 反轉兩個節點

另外提一下,這邊使用哨兵節點來處理會更好,可以避免需要特別處理 m=1 時的特殊狀況。

class Solution {
public:

    ListNode* reverseBetween(ListNode* head, int m, int n) {
            ListNode *dummy = new ListNode(0), *pre = dummy;
            dummy -> next = head;


      for (int i = 0; i < m - 1; i++) {
          pre = pre -> next;
      }
      ListNode *new_tail = pre -> next;

      for (int i = 0; i < n - m; i++) {
            // 將上一輪的頭節點存下來
            ListNode* temp = pre -> next;
            // 現象 1
            pre -> next = new_tail -> next;
            // 現象 2
            new_tail -> next = new_tail -> next -> next;
            // 新一輪的頭節點接往上一輪的頭節點
            pre -> next -> next = temp;
        }
        return dummy -> next;
    }
};

這 3 個任務並沒有一定的先後順序,只要確保每個動作執行完後,所有節點都不會變成孤兒就可以了,以下提供另外一種實作, walker 指標用來走訪反轉區間,他走到哪就要反轉到哪。

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (head == nullptr || head->next == nullptr)
            return head;
        if (m==n)
            return head;

        ListNode *dummy = new ListNode(0), *prev = dummy;
        dummy->next = head;

        for (int i=1; i<m; i++)
        {
            prev = prev->next;
        }
        ListNode *new_tail = prev->next;
        ListNode *walker = new_tail->next;

        for (int i=m; i<n; i++)
        {
            new_tail->next = walker->next;
            walker->next = prev->next;
            prev->next = walker;
            walker = new_tail->next;
        }
        return dummy->next;
    }
};

Leetcode #25 Reverse Nodes in k-Group

每 k 個節點為一個 group 進行反轉。

遞迴寫法

這題可以視為 #92 的進階題。
1. 每次都先走 k 步確認有足夠多的數量可以進行反轉。
2. 進行反轉後需要將新的 head 節點回傳回去,以利接起整個 linked list 。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (k==1)
            return head;

        ListNode *walker = head;
        for (int i = 0; i<k; i++)
        {
            if (walker != nullptr)
            {
                walker = walker->next;
            }
            else
            {
                // If number of left nodes is smaller than k, just return.
                return head;
            }
        }

        ListNode *new_head = reverseN (head, k);
        head->next = reverseKGroup (walker, k);

        return new_head;
    }
private:
    ListNode *successor = NULL;
    ListNode* reverseN (ListNode *head, int k)
    {
        if (k==1)
        {
            successor = head->next;
            return head;
        }
        ListNode *new_head = reverseN (head->next, k-1);
        head->next->next = head;
        head->next = successor;
        return new_head;
    }
};

非遞迴寫法

主要分為兩步驟:
1. 先走訪整個 list 找出 list 的總長度。
2. 透過 for loop 依序 swap 每個 group ,已經知道 list 的總長度,就可以控制總共要 swap 多少個 group 。

延伸練習

  • Leetcode #234, #143

結論

在處理 linked list 問題時,最重要一點就是不要讓任何節點變成孤兒,了解題目後,把題目需要的操作列出來,確認都有執行且執行過程不會讓任何節點變為孤兒,那就可以放心透過遞迴或是 iterative 的模式操作。