递归反转Linked List代码故障求助：输入1 2 3 -1后输出仅为1

Hey there! I see the issue with your recursive linked list reversal right away—let's break this down step by step.

The Core Problem #

When you call rev_LL(head) in your main function, you're not capturing the new head of the reversed list that the function returns.

Here's what's happening under the hood:

• Your original list is 1 -> 2 -> 3 -> NULL
• After reversal, the new head is 3, and the original head (1) becomes the tail node with next = NULL
• But you're still using the old head pointer (which points to 1) when you call print(head)—so it only prints 1 and stops at the NULL next pointer.

Fixing this is simple: just assign the return value of rev_LL back to head:

head = rev_LL(head);

Your Fixed Code #

Here's the updated full code with the critical fix in main:

#include <iostream>
using namespace std;
class Node {
public:
    int data;
    Node *next;
    Node(int data) {
        this->data = data;
        next = NULL;
    }
};
Node *insert() {
    int data;
    cin >> data;
    Node *head = NULL;
    Node *tail = NULL;
    while (data != -1) {
        Node *n = new Node(data);
        if (head == NULL) {
            head = n;
            tail = n;
        } else {
            tail->next = n;
            tail = tail->next;
        }
        cin >> data;
    }
    return head;
}
void print(Node *head) {
    Node *temp = head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
}
Node *rev_LL(Node *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    Node *smallAns = rev_LL(head->next);
    Node *temp = smallAns;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = head;
    head->next = NULL;
    return smallAns;
}
int main() {
    Node *head = insert();
    print(head);
    cout << endl;
    cout << "After reversing the Linked list : " << endl;
    // Fix: Capture the new head of the reversed list
    head = rev_LL(head);
    print(head);
    cout << endl;
    return 0;
}

More Efficient Recursive Reversal #

Your current recursive solution works, but it has a downside: for each recursive call, you traverse the entire sublist to find the tail, which gives it a time complexity of O(n²). We can optimize this to O(n) by using the head->next pointer to avoid the traversal entirely:

Node *rev_LL_opt(Node *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    // Get the new head of the reversed sublist
    Node *newHead = rev_LL_opt(head->next);
    // Make the next node point back to current head
    head->next->next = head;
    // Set current head's next to NULL (it becomes the new tail of this sublist)
    head->next = NULL;
    return newHead;
}

This version is far more efficient because we leverage the recursive call's result to directly access the end of the reversed sublist, no loop required.

Iterative Reversal (Alternative Approach) #

If recursion isn't a requirement, an iterative approach is often more efficient (no call stack overhead) and easier to debug for some developers:

Node *rev_LL_iterative(Node *head) {
    Node *prev = NULL;
    Node *curr = head;
    Node *nextNode = NULL;
    
    while (curr != NULL) {
        // Save the next node before modifying curr's pointer
        nextNode = curr->next;
        // Reverse curr's next pointer to point to previous node
        curr->next = prev;
        // Move prev and curr forward for the next iteration
        prev = curr;
        curr = nextNode;
    }
    // prev is now the new head of the reversed list
    return prev;
}

Tips to Avoid Such Mistakes #

• Always capture return values for list operations: Functions that modify the list structure (like reversal, insertion at head) often return a new head—never ignore this!
• Draw diagrams: Sketch out the linked list and pointer changes for small test cases (e.g., 2 nodes, 3 nodes) to visualize exactly what's happening.
• Test edge cases first: Validate your code with empty lists, single-node lists, and two-node lists—these often expose bugs quickly.
• Add debug prints: Temporarily print node data and pointer addresses during execution to track where your logic deviates from expected behavior.

Linked List Basics to Remember #

• The head pointer is your entry point to the list—if it changes (like in reversal), you must update your reference to it.
• Always handle NULL pointers to avoid crashes (your recursion base case does this well!).
• Reversing a list boils down to reassigning next pointers: each node should point to its previous node instead of the next one.
• For recursive solutions: define a clear base case (when to stop recursing) and ensure each recursive step solves a smaller subproblem.

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