递归反转链表代码异常：反转后仅输出首节点问题排查

你的递归反转链表代码存在核心问题：最外层的头指针（main中的head）未被更新为反转后的新头节点。反转完成后，新头节点是原链表的尾节点（6），但你的代码没有让head指向它，反而原头节点（1）的next被设为nullptr，导致printList仅输出1。

问题原因分析 #

在你的reverseList函数中，仅在递归到最底层节点时，会将当前递归层级的list参数设为原尾节点，但这个list只是上层节点next指针的引用，无法传递到最外层的head。当递归回到最外层时，head仍指向原头节点1，而1的next已被设为nullptr，因此只能输出1。

两种修复方案 #

方案一：让函数返回新头节点（推荐，逻辑更清晰）

修改reverseList函数，使其返回反转后的新头节点，在main中直接更新head：

nodePtr reverseList(nodePtr list) {
    // 空链表或仅一个节点，直接返回当前节点作为新头
    if (list == nullptr || list->next == nullptr) {
        return list;
    }
    // 递归反转剩余链表，获取新头节点
    nodePtr newHead = reverseList(list->next);
    // 调整当前节点的指向：让下一个节点的next指向自己
    list->next->next = list;
    // 当前节点作为新链表的尾节点，next设为nullptr
    list->next = nullptr;
    // 返回新头节点
    return newHead;
}

// main中的调用修改为：
head = reverseList(head);

方案二：通过引用更新最外层头指针

保持函数为void类型，调整逻辑让最外层的list引用指向新头节点：

void reverseList(nodePtr &list) {
    if (list == nullptr || list->next == nullptr) {
        return;
    }
    nodePtr rest = list->next;
    reverseList(rest);
    list->next->next = list;
    list->next = nullptr;
    // 将list更新为反转后的新头节点
    list = rest;
}

修复后完整代码示例（方案一） #

#include <iostream>

using namespace std;

struct Node {
    int data;
    Node * next;
};

typedef Node* nodePtr;

nodePtr reverseList(nodePtr list) {
    if (list == nullptr || list->next == nullptr) {
        return list;
    }
    nodePtr newHead = reverseList(list->next);
    list->next->next = list;
    list->next = nullptr;
    return newHead;
}

void insertEnd(nodePtr &list, int data) {
    nodePtr temp = new Node;
    temp->data = data;
    temp->next = nullptr;
    if (list == nullptr) {
        list = temp;
    }
    else {
        nodePtr temp2 = list;
        while(temp2->next != nullptr) {
            temp2 = temp2->next;
        }
        temp2->next = temp;
    }
}

void printList(nodePtr list) {
    nodePtr temp = list;
    cout << "The list is: " << endl;
    while (temp != nullptr) {
        cout << temp->data << endl;
        temp = temp->next;
    }
}

int main() {
    nodePtr head = nullptr; // 简化初始化，避免内存泄漏
    insertEnd(head, 1);
    insertEnd(head, 2);
    insertEnd(head, 3);
    insertEnd(head, 4);
    insertEnd(head, 5);
    insertEnd(head, 6);
    printList(head);
    head = reverseList(head);
    printList(head);
}

注：原main中nodePtr head = new Node; head = nullptr;会造成内存泄漏，已简化为直接初始化head = nullptr。

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