反向输出单链表：JavaScript 递归与循环解法实战解析

导读

在 JavaScript 中处理链表结构时，"反向输出"是一个兼具思维训练与工程价值的问题。本文以《现代 JavaScript 教程》（zh.javascript.info）递归章节中的经典练习题"反向输出单链表"为线索，完整讲解基于递归与**循环（迭代）**两种思路的解法实现，并结合仓库源码深入剖析递归调用背后的执行上下文堆栈原理、递归深度限制，以及两种解法在代码简洁性与资源消耗上的本质差异。读完本文，你将掌握单链表反向遍历的两种典型范式，并能依据实际场景权衡递归与循环的取舍。

问题背景：单链表结构回顾

在递归和堆栈章节中，我们了解到链表是一种递归定义的数据结构：每个链表元素是一个对象，包含 value 值以及指向下一个链表元素（或代表末尾的 null）的 next 属性。本任务要求针对如下链表，编写函数反向输出其元素（即依次输出 4, 3, 2, 1）：

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

本任务是前一个任务"输出一个单链表"（task.md）的进阶版：正向输出时，递归与循环都可以"边遍历边输出"；而反向输出则要求我们先处理链表末尾的元素，再处理头部的元素，这对两种实现都提出了新的挑战。

递归解法：先深入，再回溯

解法思路

递归解法的关键在于调整输出时机。正向输出时，我们先输出当前元素、再递归处理 list.next；反向输出时则必须反过来——先递归处理 list.next，等递归调用返回后再输出当前的 list.value：

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printReverseList(list) {

  if (list.next) {
    printReverseList(list.next);
  }

  alert(list.value);
}

printReverseList(list);

其执行流程如下：

1. 调用 printReverseList(list)，此时 list.value === 1。因为 list.next 存在，先不输出，转而调用 printReverseList(list.next)；
2. 依次深入 value: 2、value: 3 的节点，每次都将输出动作推迟到更深层的递归返回之后；
3. 当递归到达 value: 4 的节点时，list.next === null，不再产生新的递归调用，于是先输出 4；
4. 随后各层调用依次"回溯"，按 3 → 2 → 1 的顺序输出。

可以看到，递归解法利用函数调用栈天然实现了"后进先出"（LIFO），因此代码极为简洁——无需任何辅助数据结构，只需把 alert 放在递归调用之后即可。

递归背后的执行上下文堆栈

递归解法"看起来简单"，但它的运作机制恰恰是执行上下文与堆栈一节所讲解的核心原理：

• 每个正在运行的函数都关联一个执行上下文（内部数据结构），其中记录了当前控制流位置、局部变量等信息；
• 当函数产生嵌套调用时，当前上下文被暂停并压入执行上下文堆栈，随后为子调用创建新上下文；
• 子调用结束后，前一个上下文从堆栈中弹出，函数从暂停位置恢复执行。

在 printReverseList 中，每一次递归调用都会把"尚未执行的 alert(list.value)"连同该节点的 value 一起保存在堆栈中。链表有多长，堆栈中就会积累多少个这样的上下文——这正是"递归解法实际上也是这样做的：它顺着链表，记录每一个嵌套调用里链表的元素（在执行上下文堆栈里），然后输出它们"这句注释的技术含义。

递归深度的限制

递归解法虽然优雅，但必须清醒认识到递归深度受限：本示例的递归深度等于链表长度 n。根据章节文档的说明，JavaScript 引擎在最大递归深度为 10000 及以下时是可靠的，部分引擎允许更大深度，但 100000 往往就会超出限制（尾部调用优化尚未被普遍支持）。因此，对于超长链表，递归方案存在栈溢出的风险——这也是循环解法在实际工程中更受青睐的原因之一。

循环解法：借助数组实现反向

解法思路

单链表是单向的：每个节点只保存指向下一个节点的引用，没有任何途径直接获取"最后一个值"，也无法"从后向前"读取。因此，循环解法的策略是：

1. 正向遍历链表，把每个节点的 value 依次压入一个数组；
2. 反向遍历该数组，逐个输出元素。

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printReverseList(list) {
  let arr = [];
  let tmp = list;

  while (tmp) {
    arr.push(tmp.value);
    tmp = tmp.next;
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    alert( arr[i] );
  }
}

printReverseList(list);

这里有两个值得注意的实现细节：

• 使用临时变量 tmp 遍历：正如前一个任务的循环解法所强调的，函数入参 list 代表链表本身，应保持原样以便函数未来可被扩展复用；tmp 则扮演 for 循环中 i 那样的"游标"角色，负责完整走遍整条链表。
• 数组是"显式的栈"：while 循环将元素按正序压入数组，for 循环再从 arr.length - 1 倒序取出，实际上是用数组显式地模拟了递归中隐式的调用栈，只是这个过程完全由循环控制，不消耗函数调用栈资源。

时空复杂度对比

两种解法都遍历了整条链表，时间复杂度均为 O(n)，但资源消耗模式截然不同：

维度	递归解法	循环解法
反向机制	隐式利用执行上下文堆栈（LIFO）	显式使用数组存储元素
额外空间	O(n) 个执行上下文（受引擎递归深度限制）	O(n) 的数组（仅受内存限制）
代码简洁度	极简，仅需调整 alert 位置	需要两个循环 + 一个数组
适用场景	链表较短、强调代码可读性	链表较长、追求稳定与可预测性

值得一提的是，循环方案中用于存储的数组同样占用 O(n) 空间——它与递归方案的差异不在于"是否需要额外空间"，而在于空间被消耗在何处：递归消耗的是受限的函数调用栈，循环消耗的是普通堆内存。这也是文档反复强调"循环更有效""循环不会为嵌套函数调用消耗资源"的原因。

与正向输出的对比：两种方向，同一内核

将本任务与前一任务（正向输出）放在一起对比，可以更清晰地看到递归与循环的对称之美：

• 正向递归：alert(list.value) 在前，printList(list.next) 在后——先输出当前，再深入；
• 反向递归：printReverseList(list.next) 在前，alert(list.value) 在后——先深入，回溯时输出；
• 正向循环：while (tmp) 内边取边输出；
• 反向循环：while (tmp) 只负责收集到数组，再用倒序 for 输出。

正如04-output-single-linked-list 的递归解法所总结的：递归解更简洁、更易理解，而循环解在技术层面更高效——这一结论对反向输出同样成立。在实际工程中，链表长度可控且追求可读性时可放心使用递归；面对可能很长的链表或对性能敏感的场景，循环 + 辅助数组是更稳妥的选择。

总结

反向输出单链表是理解"递归与循环等价互换"这一核心思想的经典练习：

• 递归解法把输出动作推迟到递归调用之后，借助执行上下文堆栈天然实现"后进先出"，代码最简洁；但递归深度受引擎限制（通常 10000 以内可靠），长链表存在栈溢出风险；
• 循环解法先正序遍历并将元素存入数组，再倒序输出，用显式的数组模拟隐式的调用栈，资源消耗更可控，是长链表场景的稳妥之选；
• 两种解法的本质一致：都需要"记住"沿途经过的节点，只是记忆的载体不同——一个是函数调用栈，一个是数组。

本任务对应的完整题目与解答位于仓库 05-output-single-linked-list-reverse 目录（task.md 与 solution.md），读者可结合递归和堆栈章节中的链表定义与执行上下文讲解，完整消化这一知识点。