c - 在 C 中使用递归反转链表

Question

我是 C 的新手，我正在尝试创建一个函数来反转链表，仅将列表本身作为参数传递。如果不将节点作为参数传递，是否可以做到这一点？

到目前为止，这是我的代码，我知道它不能正常工作，因为我不知道如何对列表的其余部分进行递归调用。

void reverse(LL_t *L) {
    if (L->head->next == NULL) {
        return;
    }

    node_t *rest = L->head->next;
    reverse(rest);
    node_t *q = rest->next;
    q->next = rest;
    rest->next = NULL;
}

这里还有我的类型定义。

typedef struct {
    node_t *head;
    node_t *tail;
} LL_t;

typedef struct _node {
    int data;
    struct _node *next;
} node_t;

Answer 1

您可以用一个简单的循环来反转列表，不需要递归并且给定您的 API，这不合适。

这是您的函数的修改版本:

void reverse(LL_t *L) {
    node_t *prev = NULL;
    node_t *curr = L->head;
    L->tail = curr;
    while (curr != NULL) {
        node_t *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    L->head = prev;
}

如果你需要使用递归，你可以测试列表是否为空或限制为单例并且什么也不做，否则删除头部元素，反转结果列表并将元素追加到末尾:

void reverse(LL_t *L) {
    if (L->head != L->tail) {
        /* at least 2 elements */
        node_t *node = L->head;
        L->head = node->next;
        node->next = NULL;
        reverse(L);
        L->tail = L->tail->next = node;
    }
}

请注意，如果列表太长，这种递归方法可能会有未定义的行为，因为 reverse 会递归太多次并导致堆栈溢出。