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」提供的示意图：

我们需要交换的重点在於将「指向下一个 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）」的方法，递回是许多程序开发的第一个或第二个可能遇到的门槛，也蛮适合的在这个题目中感受看看的。

举一反三看看相似题

最後可以从题目提供的相似题看一下有哪些类似的题目，适合作为你下一个尝试的练习：

• 92. Reverse Linked List II
• 234. Palindrome Linked List

嗨，大家好！我是维元，一名擅长网站开发与资料科学的双栖工程师，斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。