算法面試套路｜原地反轉鏈表（In-place Reversal of Linked-List）

本篇內容主要為 Grokking the Coding Interview: Patterns for Coding Questions 的翻譯與整理，行有餘力建議可以購買該專欄課程閱讀並在上面進行練習。

重點整理

• 原地反轉鏈表（In-place Reversal of Linked-List）
• 策略：使用現有的節點物件實例，而不使用額外的記憶體
• 題型：
  • 樹的逐層順序遍歷
  • 樹的層級相關操作

題目匯總

• 0025 Reverse Linked List II
• 0092 Reverse Nodes in k-Group

[例題] Reverse a Linked-List

問題

給定一個單向鏈結串列（singly linked-list）的頭節點，反轉此鏈結串列，撰寫一函數返回鏈結串列反轉後的頭節點。

Example

題解

為了反轉鏈結串列，我們需要每一次反轉一個節點。我們使用變數 current 在一開始指向鏈結串列的頭節點，並用變數 previous 指向遍歷過的節點，在最一開始他將指向 null。

在後續的步驟中，我們透過在向下一個節點前進之前，將當前節點 current 指向 previous 來反轉當前節點；同時，我們需要更新 previous 為剛處理過的節點。上述演算法如圖所示：

代碼

C++

class ReverseLinkedList {
 public:
  static ListNode *reverse(ListNode *head) {
    ListNode *curr = head;
    ListNode *prev = nullptr;
    ListNode *next = nullptr;
    
    while (curr != nullptr) {
      next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
    }
    
    return prev;
  }
}

Java

class ReverseLinkedList {
  public static ListNode reverse(ListNode head) {
    ListNode curr = head;
    ListNode prev = null;
    ListNode next = null;
    
    while (curr != null) {
      next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }
    
    return prev;
  }
}

JavaScript

const reverse = (head) => {
  let curr = head;
  let prev = null;
  let next = null;
  
  while (curr !== null) {
    next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  
  return prev;
}

Python

def reverse(head):
    prev, curr, next = None, head, None
    
    while curr is not None:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    
    return prev

分析

• 時間複雜度：
  $\mathcal{O}(n)$，其中
  $n$ 為鏈結串列中的節點總數
• 空間複雜度：
  $\mathcal{O}(1)$

[例題] Reverse a Sub-List

問題

給定一個鏈結串列（singly linked-list）與兩個位置 p 和 q，反轉鏈結串列中 p 至 q 之間的部分。

Example

題解

這一題遵循 原地反轉鏈表（In-place Reversal of Linked-List） 策略，我們將使用與 Reverse a Linked-List 相同的處理方式。步驟如下：

1. 省略前面 p-1 個結點，直到抵達位置 p
2. 保存第 p-1 個結點的位置，用來串起後續反轉部分鏈結串列
3. 使用 Reverse a Linked-List 的解決方法翻轉 p 到 q 之間的鏈結串列
4. 將上述翻轉的部分與 p-1 和 q+1 連結

代碼

C++

Java

class ReverseSubList {
  public static ListNode reverse(ListNode head, int p, int q) {
    if (p == q) return head;
    
    // skipping 'p-1' nodes, curr will point to 'p' node
    ListNode curr = head;
    ListNode prev = null;
    for (int i = 0; curr != null && i < p - 1; ++i) {
      prev = curr;
      curr = curr.next;
    }
    
    // focus three parts: [0, p-1] [p, q] [q+1, -1]
    ListNode lastNodeOfFirstPart = prev;
    ListNode lastNodeOfSubList = curr;
    ListNode next = null;
    
    for (int i = 0; curr != null && i < q - p + 1; ++i) {
      next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }
    
    // connect parts
    if (lastNodeOfFirstPart != null) lastNodeOfFirstPart.next = prev;
    else head = prev;
    
    lastNodeOfSubList.next = curr;
    
    return head;
  }
}

JavaScript

Python

分析

• 時間複雜度：
  $\mathcal{O}(n)$，其中
  $n$ 為鏈結串列中的節點總數
• 空間複雜度：
  $\mathcal{O}(1)$

[例題] Reverse every K-element Sub-List

問題

題解

代碼

C++

Java

JavaScript

Python

分析

• 時間複雜度：
  $\mathcal{O}(n)$，其中
  $n$ 為鏈結串列中的節點總數
• 空間複雜度：
  $\mathcal{O}(1)$

參考資料

• Coding Patterns: In-place Reversal of a Linked List | emre.me
• Inplace Linked List Reversal Pattern | Astik Anand