如何用递归实现列表反转显示？C单链表递归打印反转错误排查及永久反转方法

嘿，别慌！我来帮你排查递归打印反转链表的问题，顺便也给你讲清楚永久反转链表的两种常用方法，完全贴合C语言单链表的写法，保证和你现有代码格式一致～

一、递归打印反转链表（不修改原链表）的常见错误 #

你说第一个元素出问题，大概率是递归和打印的顺序搞反了，或者终止条件写错了。

错误写法（会导致正序打印或漏打第一个元素） #

比如很多新手会先打印当前节点再递归，这样输出的是正序；或者终止条件写错成head->next == NULL，会漏掉原链表的第一个节点：

// 错误示例1：先打印再递归，输出正序
void printReverse(Node *head) {
    if (head == NULL) return;
    printf("%d ", head->data);
    printReverse(head->next);
}

// 错误示例2：终止条件错误，漏打原链表第一个节点
void printReverse(Node *head) {
    if (head->next == NULL) {
        printf("%d ", head->data);
        return;
    }
    printReverse(head->next);
    printf("%d ", head->data);
}

正确写法（回溯时打印，实现反转输出） #

核心逻辑是先递归到链表的最后一个节点，再回溯着打印每个节点，这样就能实现反转输出，而且完全不修改原链表：

void printReverse(Node *head) {
    // 终止条件：遇到空节点就返回
    if (head == NULL) {
        return;
    }
    // 先递归处理下一个节点，直到走到链表末尾
    printReverse(head->next);
    // 回溯时打印当前节点的数据
    printf("%d ", head->data);
}

如果你的第一个元素还是有问题，检查下主函数里的调用是不是写错了（比如不小心传了head->next而不是head），或者链表的头节点初始化有问题（比如头节点是哨兵节点？如果是带头节点的链表，要传head->next进去打印）。

二、永久反转链表的两种方法 #

如果你需要永久修改链表的结构，下面两种方法都是标准写法，和你现有代码格式完全匹配：

方法1：递归版永久反转 #

思路是递归反转后续节点，再调整当前节点的指向：

// 假设你的节点结构体是typedef struct Node { int data; struct Node *next; } Node;
Node* reverseList(Node *head) {
    // 终止条件：空链表或只有一个节点，直接返回
    if (head == NULL || head->next == NULL) {
        return head;
    }
    // 递归反转当前节点之后的所有节点，得到新的头节点
    Node *newHead = reverseList(head->next);
    // 把当前节点的下一个节点的next指向当前节点，完成反转
    head->next->next = head;
    // 当前节点的next置空，避免形成循环
    head->next = NULL;
    // 返回新的头节点（原链表的最后一个节点）
    return newHead;
}

调用时要更新头指针：head = reverseList(head);

方法2：迭代版永久反转（更高效，无递归栈开销） #

用三个指针遍历链表，逐个反转节点指向：

Node* reverseList(Node *head) {
    Node *prev = NULL;   // 保存前一个节点
    Node *curr = head;   // 当前遍历的节点
    Node *nextTemp;      // 临时保存下一个节点

    while (curr != NULL) {
        nextTemp = curr->next;  // 先存下一个节点，防止遍历丢失
        curr->next = prev;      // 反转当前节点的指向
        prev = curr;            // prev指针后移
        curr = nextTemp;        // curr指针后移
    }
    return prev;  // 遍历结束后，prev就是新的头节点
}

同样，调用后要把head更新为返回的prev。

内容的提问来源于stack exchange，提问作者sadkm