LinkedList recursion problem using Javascript

Question

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.

Can you please post a dummy example of the linked list node. — AndrewL64
– AndrewL64, Commented Jan 16, 2019 at 19:06

Danyal Imran · Accepted Answer · 2019-01-16 20:17:55Z

3

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
}

edited Jan 16, 2019 at 20:17

answered Jan 16, 2019 at 19:07

Danyal Imran

2,60515 silver badges21 bronze badges

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

5 Comments

Mark Over a year ago

Think you want to test for (!node) rather than (!node.next) otherwise you don't print the last node.

fumeng Over a year ago

I'm probably misunderstanding the printing out part. In your example, if the function is given the C node first it will call itself again and then return because D is the last node. So it wouldn't print, right?

Danyal Imran Over a year ago

@fumeng, its like this, you send your linklist first node to the function (which has the value A), then the calling part is like this A->B->C->D->null. Now the method will return till the root of execution, which is in order null ->D->C->B->A, now except for null (since it will call the return; statement in the if condition), the rest will print their value, which is D->C->B->A. I hope you understand this.

fumeng Over a year ago

Thank you, that's helpful. I get some of it but I still don't understand why the method will return 'til the root of execution. That's the only part I don't get.

Danyal Imran Over a year ago

well when you code returns from null, you actually go back to the recursive call statement and then call console.log(), since no statement after that remains, a return is called behind the scenes (and this occurs many times since its recursion), therefore the statement 'till the root of execution'.

Mike · Accepted Answer · 2019-01-16 20:09:45Z

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();

Collectives™ on Stack Overflow

LinkedList recursion problem using Javascript

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related