Reversing Linked List using Recursion

Question

I want to be able to write a recursive function to reverse a linked list. Imagine that all the elements are already appended to the list.

I want to assign head->next->next to head, so the next node of node->next is the node itself. Then, when the recursion is done, assign the linked list's head (this->head) to the final node (which is head).

What also is missing is assigning the final node's next to NULL.

Will in any world something like this work? It gives a runtime/segmentation error.

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

class LinkedList{
    node *head = nullptr;
public:
    node *reverse(node *head){
        if(head->next != nullptr){
            reverse(head->next)->next = head;
        }
        else{
            this->head = head;
        }
        return head;
    }
};

So each node in your linked list has a pointer to the head of the list (this->head), in addition to the pointer to the next node? That seems non-standard (I'd expect each node to consist of just data and a pointer to the next node). You might want to include your node's structure in your question. — JaMiT
– JaMiT, Commented Jun 2, 2018 at 14:05

einpoklum · Accepted Answer · 2018-06-02 11:07:26Z

2

Note you're ignoring the case of head being nullptr itself. Also, you can't just return head... you need to return the head of the reversed list.

Try this:

node* reverse_list(node* head) {
    if (head == nullptr or head->next == nullptr) { return head; }
    auto tail = head->next;
    auto reversed_tail = reverse_list(tail);
    // tail now points to the _last_ node in reversed_tail,
    // so tail->next must be null; tail can't be null itself        
    tail->next = head; 
    head->next = nullptr;
    return reversed_tail;
}

(not tested...)

edited Jun 2, 2018 at 11:07

answered Jun 2, 2018 at 11:01

einpoklum

137k86 gold badges445 silver badges917 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Maxim Egorushkin · Accepted Answer · 2018-06-06 14:00:13Z

1

List reversing function must be tail-recursive, otherwise it is going to overflow the stack when recursing over a long list. E.g.:

node* reverse(node* n, node* prev = nullptr) {
    if(!n)
        return prev;
    node* next = n->next;
    n->next = prev;
    return reverse(next, n);
}

An iterative list reversion can be inlined more easily:

inline node* reverse(node* n) {
    node* prev = nullptr;
    while(n) {
        node* next = n->next;
        n->next = prev;
        prev = n;
        n = next;
    }
    return prev;
}

edited Jun 6, 2018 at 14:00

answered Jun 2, 2018 at 21:26

Maxim Egorushkin

138k19 gold badges201 silver badges293 bronze badges

Collectives™ on Stack Overflow

Reversing Linked List using Recursion

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related