Better way to reverse a linkedlist in javascript

Question

I tried this:

const reverseLinkedList = (head) => {
  if (!head) {
    return {
      HEAD: null,
      curr: null,
    };
  }

  // Checking if current node is the last node or not
  if (!head.next) {
    let node = new Node(head.value);
    return {
      HEAD: node,
      curr: node,
    };
  }

  let { curr, HEAD } = reverseLinkedList(head.next);

  curr.next = new Node(head.value);

  return {
    HEAD,
    curr: curr.next,
  };
};

let { HEAD } = reverseLinkedList(list.head);
console.log(HEAD);

And my Node class:

class Node {
  constructor(val) {
    this.value = val;
    this.next = null;
  }
}

here head is the main LinkedList's head, and HEAD is the head of new one. I'm using stack here. And the algorithm is in linear complexity.

Instead of creating new Node everytime, I think there is some better way to implement this. Can you suggest some other ways? Also is it possible to use queue here to achieve this?

Best not to use recursion, but if you have to there's this. Queues and stacks seem irrelevant to linked list algorithms, since LLs are lower-level data structures, usually used to implement such higher-level data structures. — ggorlen
– ggorlen, Commented Sep 15, 2022 at 5:35
Also is it possible to use queue here to achieve this Queue is First in first out, so doesn't seem relevant unless you are ok with algorithmic tweaks in there. However, there do exist iterative solution for this. — mighty_dev
– mighty_dev, Commented Sep 15, 2022 at 5:36

mighty_dev · Accepted Answer · 2022-09-15 05:42:44Z

2

If you wish to reverse the list iteratively, we

Capture current node's next node in some other temp variable.
Make current node's next point to previous node.
Store current Node as the previous one.
Move to next node with the help of temp node captured in 1^st step.
Repeat from step 1 again.

Snippet:

const reverseLinkedList = (head) => {
  let temp = head, prev = null;

  while(temp != null){
    let nextNode = temp.next;
    temp.next = prev;
    prev = temp;
    temp = nextNode;
  }

   return prev; // as this is the new head
};

answered Sep 15, 2022 at 5:42

mighty_dev

17.8k3 gold badges24 silver badges39 bronze badges

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

Collectives™ on Stack Overflow

Better way to reverse a linkedlist in javascript

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest