[Easy] 反轉鏈表 Reverse a Linked List

反轉鏈表 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