---
title: "算法面試套路｜原地反轉鏈表（In-place Reversal of Linked-List）"
description: "Patterns for Coding Questions: Depth-First Search."
image: https://i.imgur.com/Wnnr2qC.png
author: Hsins
tags: LeetCode, Coding Interview
robots:
breaks:
GA:
disqus:
---

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

<p style="text-align: center">
<img src="https://i.imgur.com/Wnnr2qC.png" height=200/>
</p>

> 本篇內容主要為 [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) 的翻譯與整理，行有餘力建議可以購買該專欄課程閱讀並在上面進行練習。

## 重點整理

- 原地反轉鏈表（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**

<p style="text-align: center">
<img src="https://i.imgur.com/QBiNhuw.png" />
</p>

### 題解

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

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

<p style="text-align: center">
<img src="https://i.imgur.com/qhkwlsH.png">
<img src="https://i.imgur.com/9DKQqBf.png">
<img src="https://i.imgur.com/FgKmXKU.png">
<img src="https://i.imgur.com/lFGGKdK.png">
<img src="https://i.imgur.com/kf5C57h.png">
<img src="https://i.imgur.com/qibrGQs.png">
<img src="https://i.imgur.com/rwQQ3GX.png">
</p>

### 代碼

#### 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**

<p style="text-align: center">
<img src="https://i.imgur.com/WPVKFra.png" />
</p>

### 題解

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

1. 省略前面 `p-1` 個結點，直到抵達位置 `p`
2. 保存第 `p-1` 個結點的位置，用來串起後續反轉部分鏈結串列
3. 使用 [Reverse a Linked-List](#例題-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](https://emre.me/coding-patterns/in-place-reversal-of-a-linked-list/)
- [Inplace Linked List Reversal Pattern | Astik Anand](https://astikanand.github.io/techblogs/coding-problem-patterns/inplace-linked-list-reversal-pattern)