iT邦幫忙

2021 iThome 鐵人賽

DAY 10
1
Software Development

LeetCode 雙刀流:Python x JavaScript系列 第 10

LeetCode 雙刀流:206. Reverse Linked List

206. Reverse Linked List

這是一個「鏈結串列(Linked List)」的題目,鏈結串列是資料結構中重要的結構之一,利用指標的方法串接節點而成。鏈結串列相比起陣列而言,不需要連續記憶體空間,適合插入刪除、但不適合查詢(最差情況需要從頭一個一個找到尾)。

先看一下題目描述

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

再搭配範例理解題目

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

在這個題目中,要求將串接而成的鏈結串列「倒序」排列,但因為鏈結串列「相連」的特性,需要思考怎麼操作才能實現倒序的結果。

開始實作

在理解完題目與條件之後,那我們下一步就開始「#初探直覺解」並且一起嘗試「#刻意優化」的過程:

方法 ①:交換法

第一種可以透過交換的方式將指針的方向倒序,可以參考下面這張由「GeeksforGeeks」提供的示意圖:

GeeksforGeeks

我們需要交換的重點在於將「指向下一個 head.next」改成指向「前一個節點 prev」:

head.next = prev

但是為了實現所有的點,我們需要保存一些原有的資訊。因此操作上對每一個點來說,有三個指針:

  • head:指向自己
  • head.next:指向下一個
  • prev:指向前一個

我們需要將三個指針交換成:

  • head:指向自己 → 指向下一個(head.next)
  • head.next:指向前一個(prev)
  • prev:指向前一個 → 指向自己(head)

那我們先用 Python 實作看看

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        while head:
            next = head.next
            head.next = prev
            prev = head
            head = next
        return prev

也可以用 JavaScript 復刻一次

var reverseList = function(head) {
    let prev = null;
    while (head) {
        next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev; 
};

不過其實這裡在做的是「三數交換」,可以不需要 temp 變數,簡化為以下的寫法即可:

# Python
while: head.next, prev, head = prev, head, head.next

# JavaScript
while (head) [head.next, prev, head] = [prev, head, head.next];

方法 ②:遞迴(recursion)

第二種方法是遞迴(recursion),概念是「先把下一個記起來,將自己反過來指向前一個」,然後下一個持續執行直到沒有下一個為止。因為每個點的步驟是類似,因為可以將下一個持續執行的動作利用遞迴實現。

那我們先用 Python 實作看看

class Solution:
    def reverseList(self, head: Optional[ListNode], prev=None) -> Optional[ListNode]:
        if not head: return prev
        next = head.next # 先把下一個記起來
        head.next = prev # 將自己反過來指向前一個
        return self.reverseList(next, head)

也可以用 JavaScript 復刻一次

var reverseList = function(head, prev=null) {
    if(!head) return prev;
    let next = head.next; // 先把下一個記起來
    head.next = prev; // 將自己反過來指向前一個
    return reverseList(next, head);
};

反思沉澱

這題就開始導入鏈結串列(Linked List)的題目,關於鏈結串列必須了解其定義、特性跟一些常見的操作方法(包含「新增」、「刪除」或是「倒轉」之類的動作)。而「方法 ②:遞迴(recursion)」的方法,遞迴是許多程式開發的第一個或第二個可能遇到的門檻,也蠻適合的在這個題目中感受看看的。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目,適合作為你下一個嘗試的練習:


嗨,大家好!我是維元,一名擅長網站開發與資料科學的雙棲工程師,斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師,同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗,持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享,邀請你加入 訂閱 接收最新資訊。


上一篇
從內建容器到善用資料結構特性
下一篇
LeetCode 雙刀流:700. Search in a Binary Search Tree
系列文
LeetCode 雙刀流:Python x JavaScript30

1 則留言

0
TD
iT邦新手 4 級 ‧ 2021-09-25 22:12:06

那個交換法的動畫太厲害了!

我要留言

立即登入留言