尝试递归反转作为参数传递的链表而不对其进行修改，返回一个新链表

我不认为在您的尝试中存在以下所有明显限制的情况下这是不可能的：

• 递归的
• 单程通
• 没有助手或内部功能
• 无法修改函数签名（参数和返回类型）
• 不使用额外的空间

问题是，您必须跟踪在调用堆栈底部创建的新头，同时还要访问最近的上一个节点，以便您可以设置其下一个节点。

选项（每个选项都打破了上述约束之一，除了第一个选项外，大多数选项都不好）：

1. 以迭代方式进行，无论如何都更好（更容易编码，因为所有状态都是可访问的，开销更少，没有堆栈溢出的风险）。
2. 线性分两次完成：一次是复制链表，另一次是使用任何就地链表反转算法反转链表。
3. 使用内部函数或辅助函数执行此操作，该函数支持一次返回两个节点（如下所示）。
4. 使用内部函数来修改闭合中的头部（如下所示）。
5. 将状态保留在默认参数中，您希望顶级调用方不会触及该参数（如下所示）。
6. 通过返回头部并反复走到其尾巴以将其延长一个节点来二次进行。

下面是选项 3，使用帮助程序或内部函数打包两个返回值：

/**
 * @template T
 * @typedef {{readonly val: T, readonly next?: ListNode<T>}} ListNode<T>
 */
/**
 * @template T
 * @typedef {{readonly val: T, next?: ListNode<T> | null}} MutableListNode
 */

/**
 * @template T
 * @param {ListNode<T>} ll
 * @returns {ListNode<T> | null}
 */
const reverseLL = ll => {
  /**
   * @param {ListNode<T>} ll
   * @returns {{head: ListNode<T>, prev: MutableListNode<T>}}
   */
  const reverse = ll => {
    if (!ll) {
      return null;
    }
    else if (!ll.next) {
      const head = {val: ll.val};
      return {head, prev: head};
    }

    const {head, prev} = reverse(ll.next);
    prev.next = {val: ll.val, next: null};
    return {head, prev: prev.next};
  };

  return reverse(ll)?.head ?? null;
};

console.log(reverseLL(null));
console.log(reverseLL({val: 1}));
console.log(reverseLL({val: 1, next: {val: 2}}));
console.log(reverseLL({val: 1, next: {val: 2, next: {val: 3}}}));
const ll = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: {val: 4}
    }
  }
};
console.log(reverseLL(ll));

更好的是，利用闭合来跟踪头部（选项 4）：

/**
 * @template T
 * @typedef {{readonly val: T, readonly next?: ListNode<T>}} ListNode<T>
*/

/**
 * @template T
 * @param {ListNode<T>} ll
 * @returns {ListNode<T> | null}
 */
const reverseLL = ll => {
  let head = null;

  /**
   * @param {ListNode<T>} ll
   * @returns {{val: any, next?: null | {val: any, next?: null}}}
   */
  const reverse = ll => {
    if (!ll) {
      return null;
    }
    else if (!ll.next) {
      return head = { val: ll.val, next: null };
    }

    const prev = reverse(ll.next);
    prev.next = { val: ll.val, next: null };
    return prev.next;
  };

  reverse(ll);
  return head;
};

console.log(reverseLL(null));
console.log(reverseLL({ val: 1 }));
console.log(reverseLL({ val: 1, next: { val: 2 } }));
console.log(reverseLL({ val: 1, next: { val: 2, next: { val: 3 } } }));
const ll = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: {
        val: 4
      }
    }
  }
};
console.log(reverseLL(ll));

这是另一个选项 （5），将状态保留在我们期望客户端忽略的参数中。我不喜欢这样，但如果禁止内部或辅助函数方法并允许添加可选参数，那当然是可能的。

const reverseLL = (ll, head={}, firstCall=true) => {
  if (!ll) {
    return null;
  }
  else if (!ll.next) {
    head.val = ll.val;
    head.next = null;
    return head;
  }

  const prev = reverseLL(ll.next, head, false);
  prev.next = {val: ll.val, next: null};
  return firstCall ? head : prev.next;
};

console.log(reverseLL(null));
console.log(reverseLL({val: 1}));
console.log(reverseLL({val: 1, next: {val: 2}}));
console.log(reverseLL({val: 1, next: {val: 2, next: {val: 3}}}));
const ll = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: {val: 4}
    }
  }
};
console.log(reverseLL(ll));

请原谅我的密钥重命名并且不使用 TS，以便提供可运行的示例。它应该很容易转换。

有时，有约束的编程会非常有趣。希望@ggorlen的回答能帮助您了解更大的图景。

type List<T> = null | {
  readonly first: T
  readonly rest: List<T>
}

在这里，我们只使用函数本身和输入列表的单个参数，reverset -

function reverse<T>(t: List<T>): List<T> {
  if (t == null)
    return null
  else if (t.rest == null)
    return t
  else
    return {
      first: reverse(t.rest)!.first,
      rest: reverse({
        first: t.first,
        rest: reverse(reverse(t.rest)!.rest)
      })
    }
}

由于这些限制，它没有针对时间/空间进行优化。如果允许变量赋值，则可以减少重复计算 -

function reverse<T>(t: List<T>): List<T> {
  if (t == null) return null
  else if (t.rest == null) return t
  const r = reverse(t.rest)! // non-null guaranteed
  return {
    first: r.first,
    rest: reverse({
      first: t.first,
      rest: reverse(r.rest)
    })
  }
}

如果允许逻辑 or，则可以折叠条件 -

function reverse<T>(t: List<T>): List<T> {
  if (t == null || t.rest == null) return t
  const r = reverse(t.rest)!
  return {
    first: r.first,
    rest: reverse({
      first: t.first,
      rest: reverse(r.rest)
    })
  }
}

如果我们允许抽象，我们可以写cons -

function cons<T>(value: T, t: List<T>): List<T> {
  return { first: value, rest: t }
}

function reverse<T>(t: List<T>): List<T> {
  if (t == null || t.rest == null) return t
  const r = reverse(t.rest)!
  return cons(
    r.first,
    reverse(cons(
      t.first,
      reverse(r.rest),
    ))
  )
}

最后，如果允许抽象，我们可以编写其他列表操作，例如fold -

function fold<T,R>(t: List<T>, state: R, func: (value: T, state: R) => R): R {
  if (t == null)
    return state
  else
    return fold(t.rest, func(t.first, state), func)
}

const add = (a, b) => a + b

const mylist = cons(1, cons(2, cons(3, null)))

console.log("sum", fold(mylist, 0, add))

6

现在我们可以推导为reversefoldcons -

function reverse<T>(t: List<T>): List<T> {
  return fold(t, null as List<T>, cons)
}

我们可以使用另一个我们可以欣赏的列表操作来可视化输出，toString -

function toString<T>(t: List<T>): string {
  if (t == null)
    return "∅"
  else
    return String(t.first) + " -> " + toString(t.rest)
}

const mylist = cons(1, cons(2, cons(3, cons(4, cons(5, null)))))

console.log(toString(mylist))
console.log(toString(reverse(mylist)))
console.log(toString(mylist))

重新打印原始列表显示你是一个不可变的操作——reverse

1 -> 2 -> 3 -> 4 -> 5 -> ∅
5 -> 4 -> 3 -> 2 -> 1 -> ∅ 
1 -> 2 -> 3 -> 4 -> 5 -> ∅