[Leetcode] Linked List 介紹

7 min readJun 27, 2020

基本介紹

這個章節我們來講解 Link List 的解題思路，在解題前要先了解 Link List 的特性，如下圖所示：

通常你只會知道某一個節點的位置，而題目通常會給你整個 List 的頭叫做 Head，而不知道的事情有：

1. 不知道整個 List 長度為何
2. 不知道第一個節點以外的其他節點的值與位置，而且沒辦法直接 Access
3. 連結是上一個節點接到下一個節點，以上圖來說如果現在3的位置，會不知道上一個是1

資料結構

Leetcode 給的資料結構為：

Java

public class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

C++

struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

Python

class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

Leetcode 出題方向

Link List 有一個明顯的特性是擁有一個指標，並且他的限制如同上面所提到的三個不知道的事情，因此題目方線都會傾向於指標的改動，而指標的改動就包含刪除節點、交換節點、分堆、排序等題目，我們可以一一來看：

刪除節點

0019. Remove Nth Node From End of List > 刪除倒數第 N 個節點
— — 因為不知道整個 List 的長度，所以做這件事特別麻煩。

0082. Remove Duplicates from Sorted List II > 刪除值重複的節點 (sorted)
— — 不知道上一個節點的位置，以至於不知道上一個值和這一個值是不是一樣的。

1171. Remove Zero Sum Consecutive Nodes from Linked List > 連續加總為0的都刪掉
— — 要記錄每一段連續的 List 的頭尾位置在哪裡。

交換節點

0024. Swap Nodes in Pairs > 兩兩交換 (1, 2)換, (3, 4)換
— — 除了值交換以外、指標要跟著換

List 分堆

0086. Partition List > 大於等於數字 n 的節點要放到 List 的尾巴
— — 不知道尾巴的位置在哪裡。

0328. Odd Even Linked List > index 是偶數的丟到尾巴
— — 不知道尾巴的位置在哪裡。

0725. Split Linked List in Parts > 將 List 平分成 k 組
— — 不知道 List 長度為何，不知道一組有幾個。

排序

0143. Reorder List > 重新排序成 1 → N → 2 → N-1 → …
— — 不知道尾巴的位置，也不知道尾巴的前一個N-1位置在哪裡

0147. Insertion Sort List > 用 insertion sort 來排序
— — 在插入時要更動指標

0148. Sort List > 要用 O(nlogn) 演算法做排序
— — 不能直接 Access 節點位置，感覺只能用 Merge sort

看到題目時，我們可以先思考，為什麼這會變成一道題目？他真正想要考的東西是什麼？因此當我們先列出 Link List 的特性之後，就會知道在每一個題目上可能會遇到的困難有哪些，而只要試圖解決這些困難，就有機會迎刃而解。

不知道整個 List 的長度
可能必須先花 O(n) 的時間，Traverse 一遍 List 知道長度為何
不知道上一個節點的位置
設定當前的指標 curr 以及 prev，就可以知道上一個節點的位置
不知道最後一個節點(尾巴)的位置
可能必須先花 O(n) 的時間，Traverse 一輪，當 curr.next = NULL 時，
及為 tail。
不能直接 Access 節點
不過可以用一個 Map 去紀錄每一個 index 對應的 node，就好比能直接 Access 每一個節點 → 代價是 Space 需要用到 O(n)。
更動指標的方法
A. 先找到要插入/交換的位置
B. 將每一個節點的 Next 接好
C. 更換每一個當前指標
下面可以舉一個例子為 0086. Partition List

In-place vs Non In-place

通常題目有可能要求用 In-place 的做法，因為這樣的做法會節省空間，因此會需要先設定一些指標，讓你好插入位置；而如果題目不要求的話，其實可以先把 Link List 的值都先存到 Array 當中，這樣只要用 Array 的資料結構先完成題目要求，最後再丟回 Link List 中，不過這樣就有點失去考 Link List 的意義！

小技巧

增加一個 node 叫做 pre_head 指向 head
通常題目會給你 head 指向第一個位置，但有時候第一個位置有時候會因題目要求不同，有可能更動，因此先新增一個 pre_head 指向 head，這樣就不會有 head 不見的問題。
建立有意義名稱的指標使自己不搞混
有時候在 Traverse 整個 List 的時候，會因為不同題目有不同的作法，有時候會需要 while (curr) 有時候則是 while(curr.next)，甚至是 while(curr.next && curr.next.next)，因此有時候會錯亂這個 curr 到底指的是誰，因此可以多建立幾個指標像是 prev, next 等指標，來幫助你不會錯亂 while(curr.next) → while (next)。
先把框架建立好，在寫裡面的邏輯
因為要解決一件事情的方法有無限多種可能，有好的框架可以幫助你更好的思緒該怎麼建構，因此我會先把框架建立出來，像是下面範例：