c - 反转列表会导致段错误

Question

我正在尝试递归地反转链表。我有这些结构:

typedef Test test;

typedef struct Node {
    test t;
    struct Node *nxt;
} LNode;

typedef struct {
    int size;
    LNode *first;
} L;

其中 Test 是一个包含学生姓名和成绩(考试成绩)的结构。

void recursiveReverse(L * r) {
       LNode * first;
       first = r->first; //first node in list

       reverseList(first);
}

void reverseList(LNode * first) {
    LNode * rest;
    rest = first->nxt;

    reverseList(r,rest);

    first->nxt->nxt = first;
    first->nxt = NULL;

    first = rest;
}

但是，我在尝试此操作时似乎遇到了段错误。我不允许更改函数 recursiveReverse 的参数参数，我被告知必须调用另一个函数，并将该函数用作递归调用函数(我有)。任何帮助将非常感激。

Answer 1

编写递归函数最重要的规则是它们必须终止。简单来说，必须存在递归函数不调用自身的条件。这就是所谓的“基本情况”。

对于您的列表反转函数，基本情况是您必须反转的列表部分恰好包含一个节点，因为单节点列表本身就是一个普通的反转。因此，reverseList 中需要有一个案例，您可以这样说:

if (first->nxt == NULL) {
    // Do not go into recursive invocation
    return; // This is not complete yet
}

您的代码中缺少的另一件事是反向列表将有一个新的头部，即以前作为尾部的节点。您的 reverseList 应该返回它。

编写递归函数的其余部分的一个有用技巧是想象该函数已经为您编写好了，并在知道它做什么的情况下调用它，暂时忘记 em>它是怎么做到的。在列表反转的情况下，递归步骤相对简单:您获得反转列表的头部，然后更改当前节点的下一个以指向回当前节点。

LNode* reverseList(LNode* list) {
    if (list->nxt == null) {
        return list;
    }
    // Reverse the tail
    LNode *head = reverseList(list->nxt);
    // Invert this node
    list->nxt->nxt = list;
    // Return the result of tail reversal
    return head;
}

此时唯一缺少的是将新尾部的 nxt 设置为 NULL。您应该在您的 recursiveReverse 函数中执行此操作:

void recursiveReverse(L * r) {
    LNode *first = r->first;
    LNode *newHead = reverseList(first);
    first->nxt = NULL;
    r->first = newHead;
}

Demo.