如何实现无修改递归反转链表？解决中间节点丢失问题

问题描述 #

当前实现的递归反转链表函数仅支持长度≤2的链表，处理更长链表时会丢失中间节点。需要修改函数，使其能处理任意长度的链表，且不修改原链表，返回全新的反转链表。

类型定义 #

type List = null | ConsCell;

type ConsCell = {
  readonly first: number;
  readonly rest: List;
}

函数要求 #

实现reverse函数：

function reverse(list: List): List {

}

示例 #

• 输入null，输出null
• 输入{ first: 1, rest: null }，输出{ first: 1, rest: null }
• 输入{ first: 1, rest: { first: 2, rest: { first: 3, rest: null } } }，输出{ first: 3, rest: { first: 2, rest: { first: 1, rest: null } } }

当前代码问题分析 #

你当前的实现中，else分支存在逻辑错误：递归得到反转后的剩余链表oldRest后，仅取了oldRest的第一个节点，然后将当前节点直接挂在其后面并把rest设为null，导致oldRest中的后续节点全部丢失。比如处理1->2->3时，reverse(2->3)会得到3->2，但你的代码返回3->1，中间的2被丢弃了。

修复后的代码 #

function reverse(list: List): List {
  // 辅助函数：用累加器保存已反转的新链表
  const helper = (current: List, reversed: List): List => {
    if (!current) {
      return reversed;
    }
    // 创建新节点，将当前值作为新节点的first，已反转链表作为rest
    return helper(current.rest, {
      first: current.first,
      rest: reversed
    });
  };

  return helper(list, null);
}

代码说明 #

这个实现采用尾递归+累加器的方式：

1. 辅助函数helper接收两个参数：current是当前待处理的原链表节点，reversed是已经构建好的反转新链表。
2. 每次递归时，创建一个全新的节点，把当前节点的first值赋值给新节点，同时将新节点的rest指向已反转的reversed链表。
3. 递归处理原链表的下一个节点，直到原链表遍历完毕，此时reversed就是完整的反转新链表。
4. 整个过程完全不修改原链表的任何节点，所有节点都是新创建的，符合要求。

验证示例 #

对于输入1->2->3：

• 第一次递归：current=1->2->3，创建新节点1->null，递归处理2->3，累加器为1->null
• 第二次递归：current=2->3，创建新节点2->1->null，递归处理3，累加器为2->1->null
• 第三次递归：current=3，创建新节点3->2->1->null，递归处理null，累加器为3->2->1->null
• 递归结束，返回累加器，即正确的反转链表

内容的提问来源于stack exchange，提问作者ndubs18