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?

CodePudding user response：

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
};