[Easy] 反轉鏈表 Reverse a Linked List

2024年3月18日

💎 加入 E+ 成長計畫 與超過 300+ 位軟體工程師一同在社群中成長,並且獲得更多的軟體工程學習資源

反轉鏈表 reverse a linked list,是程式面試中,很常考的入門考題。

在這個面試題中,我們要把:

1 -> 2 -> 3

反轉為:

1 <- 2 <- 3

讓我們一起來看看要怎麼做吧!

實作反轉鏈表 Reverse a Linked List

首先,如果今天直接把 2 從原本指向 3、改成指向 1,就會導致 2 跟 3 之間的鏈接斷開,這時 3 就沒辦法指向 2。

1 -> 2 -> 3
1 <- 2    3

要解決這問題很簡單,可以透過記下位置來解決。這邊直接講解程式碼。

程式碼講解

function reverseList(head) {
  // 先初始化一個指標來追蹤前一個節點
  let prev = null;

  // 透過 while 迴圈迭代,從頭節點開始,只要還有當前節點,就持續迭代
  while (head) {
    let next = head.next; // 先暫時把下一個節點存在 next 變數
    head.next = prev; // 把頭節點的指向前一個節點,藉此反轉鏈表
    prev = head; // 將 'prev' 指標移到 head 節點
    head = next; // 將 'head' 指標移到 next 節點,為下一次迭代做準備
  }
  return prev; // 回傳完成後,反轉後串列的新的頭節點
}

這樣可能很抽象,讓我們具體用開頭的例子來展示

初始化 prev 這個變數,值為 null
// null  1 -> 2 -> 3
// prev  head

接著進入迴圈,用 next 變數,來記下 head.next 也就是 2 的位置
// null   1 -> 2 -> 3
// prev  head next

讓原本鏈表的 head 指向 prev
// null <- 1  2 -> 3
// prev  head

向 next 移動,prev 移動到把原本的 head
把原本的 head 移動到剛剛記下的 next
// null <- 1    2 -> 3
//       prev  head

接著,重複剛剛的步驟
用 next 變數,來記下 head.next 也就是 3 的位置
// null <- 1    2 -> 3
//        prev head next

讓原本鏈表的 head 指向 prev
// null <- 1 <- 2    3
//        prev head next

向 next 移動,prev 移動到把原本的 head
把原本的 head 移動到剛剛記下的 next
// null <- 1 <- 2    3
//             prev head next

然後 head.next 會是 prev
把原本的 head 移動到剛剛記下的 next
// null <- 1 <- 2 <- 3
//             prev head next


向 next 移動,prev 移動到把原本的 head
把原本的 head 移動到剛剛記下的 next
此時 head 是 null,我們就回傳 prev
就會是從 3 指向 2 指向 1 的鏈表了~
// null <- 1 <- 2 <- 3
//                  prev head next
🧵 如果你想收到最即時的內容更新,可以在 FacebookInstagram 上追蹤我們