Issues with reverse Linked List using recursion

Question

I'm trying to reverse a linked list using recursion. Everything goes well until the end and I end up getting broken result.

Can someone tell me what I'm doing wrong?

const reverseLinkedList = (node, newChildOldParent=null ) => {
    if( node.next ){
        reverseLinkedList(node.next, node);
    }
    node.next = newChildOldParent;
    return node;
}

const someList = {
    value: 1,
    next: {
        value: 2,
        next: {
            value: 3,
            next: {
                value: 4,
                next: null
            }
        }
    }
};

console.log(reverseLinkedList( someList ))

I get

{ value: 1, next: null }

Instead of the reversed linked List.

Where am I going wrong?

your problem is that you are reversing the list alright, but you are getting the first element again in the end (as the stack unfolds). Your first element is now the last and doesn't have a next node. — Sandro
– Sandro, Commented Aug 1, 2018 at 19:58

ggorlen · Accepted Answer · 2018-08-01 21:04:13Z

4

The reversal is working fine, but you've lost track of the new head and instead return the old head which is now pointing to null. Here's a diagram of the stack calls:

curr: 1 next: 2
  curr: 2 next: 3
    curr 3: next: 4
      curr: 4 next: null
      curr: 4 next: 3
    curr: 3 next: 2
  curr: 2 next: 1
curr: 1 next: null <-- uh oh

You need to keep track of the new head, which is node 4. Here's another approach that passes the last node back to the head:

const reverseLinkedList = (curr, prev) => {
    if (curr.next) {
        const newHead = reverseLinkedList(curr.next, curr);
        curr.next = prev;
        return newHead; // pass the new head up the list
    }
    
    curr.next = prev;
    return curr; // base case; return the tail
};

const someList = {
    value: 1,
    next: {
        value: 2,
        next: {
            value: 3,
            next: {
                value: 4,
                next: null
            }
        }
    }
};

console.log(reverseLinkedList(someList));

edited Aug 1, 2018 at 21:04

answered Aug 1, 2018 at 20:01

ggorlen

59.3k8 gold badges119 silver badges173 bronze badges

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

3 Comments

Bergi Over a year ago

Calling it newHead instead of next might be more appropriate

Bergi Over a year ago

"the (list of) next nodes", yeah why not. But it is not the next node, so it's confusing.

ggorlen Over a year ago

I see what you're saying here and agree with you--I'll update to clarify.

Collectives™ on Stack Overflow

Issues with reverse Linked List using recursion

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related