Chris's Lab

If you obey all the rules,you miss all the fun.

0%

[LeetCode] 206. Reverse Linked List

發表於 分類於 ， ， Disqus：
這是一題單向鏈結串列反轉的題目，運用指標的算法

前言

　　這是一題單向鏈結串列反轉的題目，運用指標的算法，目標是將原本的鏈結串列倒序排列，此演算有使用到一個 while 迴圈，則時間複雜度估 O(n)，這裡有 JAVA 和 Python 的寫法。

題目

Given the head of a singly linked list, reverse the list, and return the reversed list.

給定一個 head 單向鏈結串列，反轉這個串列，且回傳反轉過後的這個串列。

題目連結：https://leetcode.com/problems/reverse-linked-list/description/

題目限制

The number of nodes in the list is the range [0, 5000].
5000 <= Node.val <= 5000

範例

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

思路&筆記

鏈結串列的題目，簡單想像是在處理節點的位置，資料先放一邊別去裡他。
這裡設定三個指標分別是指向 null 的 (指標一)、指向當前 head 的 (指標二)、輔助指標 nextNode (指標三)。

  • 設定好三個指標後
  • 把當前的 curr.next 掛在輔助指標 nextNode 上 (確保在反轉的過程中不會失去原始下一個節點的位置)
  • 掛完之後把當前節點 curr.next 指向 prev (此時指針已反轉了)
  • 接下來移動指針 prev 到 curr
  • 將 curr 掛在 nextNode (剛剛保存的原始下一個節點的位置)
  • 以上邏輯循環到最後，當 curr 移動到 null 時則停止迴圈 (鏈結串列的末端節點一定會指向 null)

[補充] curr.next 同等於 curr → link (指向下一個節點的意思)

JAVA 實現

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode reverseList(ListNode head) {

        ListNode curr = head; // 當前指標 (指標一)
        ListNode prev = null; // 空集合指標 (指標二)

        // 檢查確定鏈結串列裡有資料
        while (curr != null) {
            ListNode nextNode = curr.next; // 輔助指標 (指標三)，指向下一個節點 (資料暫存在輔助指標內)
            curr.next = prev; // 將 curr 的 next 指針指向 prev，(將當前節點的指針方向反轉)
            prev = curr; // 更新指針指向：將 prev 設為 curr
            curr = nextNode; // curr 設為 nextNode
        }

        return prev;
    }
}

Python 實現

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。
(Python 中不需要再宣告一個額外的變數來存儲原始的鏈結串列)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
			
        prev = None # 空集合指標 (指標一)

        while head:
            nextNode = head.next # 輔助指標 (指標二)
            head.next = prev # 反轉
            prev = head # 移動指標
            head = nextNode # 掛回去原本的鏈結串列

        return prev

成績

Language Runtime Memory
Java 0ms 41.8MB
Python 53ms 17.9MB