使用递归错误反转链表

Question

我正在理解递归，所以我尝试编写反向链表程序。我写了下面的函数，但它说分段错误（核心转储）。

void reverse(){
    if (head -> next == NULL){
        return;
    }
    reverse (head -> next);
    struct node *q = (struct node*) malloc (sizeof(struct node));
    q = head -> next;
    q -> next = head;
    head -> next = NULL;
}

请有人指导我。谢谢。

Answer 1

不应该反驳吗？请注意，您不能更改函数中的指针并使其成为持久更改。也就是说，在 C 函数中，唯一持久的更改是那些使用 *var = something 的更改。

Answer 2

递归是一种通过实践获得的思维方式。所以祝贺你的尝试。这是不正确的，但不要气馁。

这里有两种解决问题的方法。

您的目标是将其细分为自身的较小版本加上一个（希望计算起来容易且快速）增量步骤，该步骤将较小版本的解决方案转化为完整的解决方案。这就是递归思维的本质。

首先尝试：将列表视为头元素加上 "rest of the list." 即

L = empty or
  = h . R

其中 h 是头元素 R 是列表的其余部分，点 . 是将新元素加入列表。反转此列表包括反转 R，然后在末尾附加 h：

rev(L) = empty if L is empty
       = rev(R) . h otherwise

这是一个递归的解决方案，因为我们可以递归调用反向函数来解决稍微小一点的反向问题R，然后添加一点工作来追加h，这给了我们完整的解决方案。

此公式的问题在于附加 h 比您希望的要昂贵。由于我们有一个只有头指针的单向链表，所以很耗时：遍历整个链表。但它会工作正常。在 C 中它将是：

NODE *rev(NODE *head) {
  return head ? append(head, rev(head->next)) : NULL;
}

NODE *append(NODE *node, NODE *lst) {
  node->next = NULL;
  if (lst) {
    NODE *p;
    for (p = lst; p->next; p = p->next) /* skip */ ;
    p->next = node;
    return lst;
  }
  return node;
}

那么如何摆脱糟糕的表现呢？通常情况下，问题的不同递归公式具有不同的效率。所以经常涉及一些试验和错误。

下一步尝试：考虑将列表分成两个子列表的计算：L = H T，所以 rev(L) = rev(T) + rev(H)。这里加上+就是列表拼接。关键是，如果我知道 rev(H) 并且想在其头部 添加一个新元素 ，则要添加的元素是 first T 中的元素。如果这看起来很模糊，让 H = [a, b, c] 和 T = [d, e]。那么如果我已经知道 rev(H) = [c, b, a] 并且想要在头部添加下一个元素，我想要 d，它是 T 的第一个元素。在我们的小符号中，你可以写下这个观察就是这样：

rev(H + (d . T)) = rev(T) + ( d . rev(H) )

所以这看起来非常好。在这两种情况下（获取 T 的头部并将其移动到 rev(H) 的头部），我只对列表的头部感兴趣，这是非常有效的访问方式。

当然如果T为空，则rev(H) = rev(L)。这就是答案！

将此编写为递归过程。

NODE *rev(NODE *t, NODE *rev_h) {
  if (t) {                // if t has some elements
    NODE *tail = t->next;   // save the tail of T
    t->next = rev_h;        // prepend the head to rev(H)
    return rev(tail, t);    // recur to solve the rest of the problem
  }
  return rev_h; // otherwise T is empty, so the answer is rev(H)
}

一开始，我们对rev(H)一无所知，所以T是整个列表：

NODE *reversed_list = rev(list, NULL);

接下来要注意的是这个函数是尾递归的：递归调用恰好在函数returns之前执行。这很好！这意味着我们可以轻松地将其重写为一个循环：

NODE *rev(NODE *t, NODE *rev_h) {
recur:
  if (t) {                // if t has some elements
    NODE *tail = t->next;   // save the tail of T
    t->next = rev_h;        // prepend the head to rev(H)
    rev_h = t;              // "simulate" the recursive call
    t = tail;               //   by setting both args
    goto recur;             //   and going back to the start
  }
  return rev_h; // otherwise T is empty, so the answer is rev(H)
}

您始终可以使用尾递归调用来完成此转换。你应该好好想想为什么会这样。

现在 goto 很容易重写为 while 循环，我们可以将 rev_h 初始化为 NULL 的局部变量，因为这就是初始调用所做的全部工作：

NODE *rev(NODE *t) {
  NODE *rev_h = NULL;
  while (t) {             // while t has some elements
    NODE *tail = t->next;   // save the tail of T
    t->next = rev_h;        // prepend the head to rev(H)
    rev_h = t;              // "simulate" the recursive call
    t = tail;               //   by setting both args
  }
  return rev_h; // otherwise T is empty, so the answer is rev(H)
}

一个就地链表逆向器，只需要少量常量space！

看！我们从来不需要画有趣的方框和箭头图，也不需要考虑指针。它"just happened"通过仔细推理如何将问题本身细分为更小的实例，递归的本质。这也是了解循环只是一种特殊递归的好方法。很酷，不是吗？

Answer 3

我假设您在 .c 文件中预定义了如下内容

typedef struct node node_t;
struct node {
    int some_data;
    node_t *next;
};

/* Your linked list here */
typedef struct {
    node_t *head;
    node_t *foot; /* to keep track of the last element */
} list_t;

在你的函数中，你犯了一些错误

不提供任何输入参数
当程序不知道去哪里找head时访问head->next

因此，导致了 C 中最令人沮丧的错误——分段错误！

相反，您应该尝试以下操作：

void reverse(list_t *mylinkedlist){
    if (mylinkedlist->head->next == NULL) {
        return;
    }
    /* do something */
}

使用递归错误反转链表

reverse a linked list using recursion error

c

recursion

linked-list