CODEWITHSUNDEEP
javascript
fumeng
fumeng

Reputation: 1820

LinkedList recursion problem using Javascript

Looking for help solving this recursion problem: Given a linked list of indeterminate length, composed of nodes that store a reference to the next node....how can you return the list in reverse?

For example, node A --> B --> C --> D should return D-->C-->B-->A. The function is given any node and should return that list in reverse.

A node would consist of a couple values; an integer (i) and a next property which is the pointer to the next node. 

const traverseList = (node) => {
    if(node.next !== null) traverseList(node);
    else return;
}

I'm trying this code but it's not working. Just looking for the missing pieces, please. Thanks for any help.

Upvotes: 0

Views: 627

Answers (2)

Danyal Imran
Danyal Imran

Reputation: 2605

you are on the right path, just print it when you are returning from each node.

const traverseList = (node) => {
   if (!node) return;

   traverseList(node.next);
   console.log(node.value); // or whatever you want to output
}

Upvotes: 3

Mike
Mike

Reputation: 617

1) Store a reference to current(initially head), next(initially null), previous(initially null) node

2) Set tail to head, if your using a tail pointer

3) Traverse this list setting next to current.next, current.next to previous, previous to current, and finally current to next

4) Depending on how you do it after the loop, you must set current.next to previous and head to current

I have included both iterative and recursive solutions below.

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

class LinkedList {
 constructor(){
  this.size = 0;
  this.head = null;
  this.tail = null;
 }
 
 add(value){
  const node = new Node(value, null);
  
  if(this.head === null){
   this.head = node;
   this.tail = node;
  } else {
   this.tail.next = node;
   this.tail = node;
  }
  
  this.size++;
 }
 
 traverse(){
  let current = this.head;
  
  while(current != null){
   console.log(current.value);
   current = current.next;
  }
 }
 
 reverse(){
   let current = this.head;
   let previous = null;
   let next = null;
   this.tail = current;
   
   while(current != null && current.next != null){
      next = current.next;
      current.next = previous;
      previous = current;
      current = next;
   }
   
   current.next = previous;
   this.head = current;
 }
 
 _reverseRecursively(node){
  if(node == null){
   return null;
  }
  
  if(node.next == null){
   this.head = node;
   return node;
  }
  
  let nextNode = this._reverseRecursively(node.next);
  nextNode.next = node;
  node.next = null;
  return node;
 }
 
 reverseRecursively(){
  this.tail = this.head;
  this._reverseRecursively(this.head);
 }
}

const list = new LinkedList();

list.add(10);
list.add(12);
list.add(14);
console.log("Original List");
list.traverse();
list.reverse();
console.log("Reversed List - using loop");
list.traverse();
list.reverseRecursively();
console.log("Reversed List - using recursion");
list.traverse();

Upvotes: 1

Related Questions