[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