5

在一次工作面试中，我被要求用 C 编写一个函数，它递归地反转一个链表，返回新的第一个节点，并且不使用任何新节点。

你怎么能做到这一点？

4

5 回答 5

3

这是一般的想法，使用类似 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 的答案），否则您不能同时消除两者并有一个可行的算法。最好谨慎行事，并使用临时变量来执行评估顺序并始终获得正确的结果。

于 2012-10-03T01:21:17.773 回答
3

这很简单：递归到链表尾，next每次传入新指针，返回链表尾。

struct list {
    struct list *next;
};

struct list *reverse(struct list *cur, struct list *prev) {
    struct list *next = cur->next;
    cur->next = prev;
    if(next == NULL) return cur;
    return reverse(next, cur);
}

reverse(head, NULL);
于 2012-10-03T01:21:51.440 回答
2

我不知道什么是“递归链表”，所以我将使用您的标题并假设您想使用递归函数“反转链表”。

我假设它是一个单链表（所以每个元素都有一个指向next下一个元素的指针）并且按照惯例取next = NULL最后一个元素。 对于双向链表，您还必须处理prev指针，但它基本上是相同的想法。 使用双向链表会更简单，因为您甚至不需要跟踪前一个元素；您只需在每个元素上翻转两个指针。

要反转列表，我们可以想象一次向下遍历一个元素，同时翻转next指针以指向前一个元素。这很容易写成一个递归函数，它接受一个指向当前元素的指针和一个指向前一个元素的指针作为参数（在开始时这个指针是NULL）。

node* reverseList(node* head, node* prev = NULL) {
  if (head == NULL) return prev;

  std::swap(head->next, prev); // prev points to next element to process
  return reverseList(prev, head);
}
于 2012-10-03T01:38:13.460 回答
1

嘿伙计们，请在下面找到带有和不带有递归的反向链表程序

LINK *reverse_linked_list_recursion(LINK *head)
{
        LINK *temp;
        if (!head) {
                printf("Empty list\n");
                return head;
        }
        else if (!head->next)
                return head;
        temp = reverse_linked_list_recursion(head->next);
        head->next->next = head;
        head->next = NULL;
        return temp;
}

LINK *reverse_linked_list_without_recursion(LINK *head)
{
        LINK *new, *temp;
        if (!head) {
                printf("No element in the list\n");
                return head;
        }
        else {
                new = head;
                while (head->next) {
                        temp = head->next;
                        head->next = temp->next;
                        temp->next = new;
                        new = temp;
                }
        }
        return new;
}
于 2013-08-13T06:49:59.060 回答
0

所以，奥斯卡洛佩兹的答案的变化是

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

表达式序列(a,b)返回其最后一个值并从左到右进行计算。

这仅适用于保证函数参数的评估顺序为left-to-right的编译器。如果它是right-to-leftinvert ，则应交换to 的参数

如果评估顺序是不确定的，这将不起作用。C 标准显然未指定此顺序，但某些编译器可能有自己的方式。你可能知道你的编译器，但它是不可移植的，你的编译器将来也可能会改变它。编写这样的代码是不受欢迎的。也许这就是你的面试官想从你那里听到的。他们喜欢这样的把戏，想看看你的反应。

控制评估顺序的正常方法是使用临时变量。

于 2012-10-03T23:29:30.740 回答