反向链接列表递归不使用任何新变量

Question

在求职面试中,我被要求在C中编写一个递归反转链表的函数,返回新的第一个节点,并且不使用任何新节点.

你怎么能这样做？

Answer 1

以下是使用类似 C 语法的不可知语言的总体思路：

Node invert(Node list, Node acc) {
    if (list == null)
        return acc;
    Node next = list.next;
    list.next = acc;
    return invert(next, list);
}

上面的函数接收要反转的列表的第一个节点和到目前为止的累积值，并返回新反转的列表的头部 - 节点的反转是就地完成的，没有分配额外的空间（除了本地堆栈中的变量）。像这样称呼它：

invert(firstNodeOfList, null);

这是尾递归的一个例子：结果被收集在参数中acc，当每个递归调用返回时，没有什么可做的，只是返回累积值。

更新：

在函数式语言中，编写一个函数来反转列表而不使用局部变量会更容易、更自然，例如查看Scheme中的以下代码 - 它有一个缺点，即在调用过程时它将创建一个新的列表节点cons：

(define (invert lst acc)
  (if (empty? lst)
      acc
      (invert (rest lst)
              (cons (first lst) acc))))

(invert '(1 2 3 4 5) '())
> '(5 4 3 2 1)

底线：您要么创建一个新节点，要么在每次递归调用时创建一个新的局部变量，但除非编程语言提供用于顺序执行的表达式并且编译器保证评估顺序（参见@WillNess的答案），否则您无法消除这两者并有一个可行的算法。最好谨慎行事，使用临时变量来执行评估顺序并始终获得正确的结果。