LeetCode 獨自升級紀 - [Linked List] Reverse Linked List (Easy)

題目

給定一個單向 Linked List，反轉該鏈表並返回反轉後的頭節點。

Example:

1 2	Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

觀念

反正就記得，反轉一條鏈表，就是把每個節點的 next 指標指向前一個節點

特性	Python list (`[]`)	Linked List
底層結構	動態陣列 (連續記憶體)	節點 (物件) + 指標
存取第 i 個元素	O(1)	O(n) (要走訪)
插入 / 刪除	O(n) (中間要搬移)	O(1) (只改指標)
記憶體配置	連續	不連續
適合情境	頻繁隨機存取	頻繁插入 / 刪除
5	`5 → 4 → 3 → 2 → 1 → None`	5 的 next 指向 4，curr 變 None

Linked List

class Solution:
  def reverseList(head: ListNode) -> ListNode:
      prev, curr = None, head
      while curr:
          temp = curr.next  # 先暫存下一個節點，避免斷鏈 #
          curr.next = prev  # 把 curr 的 next 指向 prev，完成反轉，變 None <- 1 <- ...
          prev = curr  # 把目前的節點 curr 指向 prev
          curr = temp  # curr 指向下一個節點
      return prev

逐步拆解執行流程：

Step	curr	temp = curr.next	執行 `curr.next = prev` 後	prev = curr	curr = temp	prev 指向的鏈表
0 (初始)	1	-	-	None	1	None
1	1	2	`1 → None`	1	2	1 → None
2	2	3	`2 → 1 → None`	2	3	2 → 1 → None
3	3	4	`3 → 2 → 1 → None`	3	4	3 → 2 → 1 → None
4	4	5	`4 → 3 → 2 → 1 → None`	4	5	4 → 3 → 2 → 1 → None
5	5	None	`5 → 4 → 3 → 2 → 1 → None`	5	None	5 → 4 → 3 → 2 → 1 → None

Time Complexity: O(n)
Space Complexity: O(1)

參考

初次學 Linked List 可能會有點抽象，這邊分享當初看到一個非常淺顯易懂的 yt 教學

YouTube - Reverse Linked List

若您覺得這篇文章對您有幫助，歡迎分享出去讓更多人看到⊂◉‿◉つ~

LeetCode 獨自升級紀 - [Linked List] Reverse Linked List (Easy)

題目

觀念

Linked List

參考

留言版

FEATURED TAGS

FRIENDS