I am trying to reverse linkedlist recursively in Javascript. I have tried myself and search the net to find it. But no success. Below is the code I tried:

var Node = (function(){
    function Node(val){
        this.elem = val;
        this.next = null;
    }
    return Node;
})();

var SLinkedlist = (function(){
    function SLinkedlist(){
        this.head = new Node("head");
    }
    return SLinkedlist;
})();

SLinkedlist.prototype.find = function(val){
    var current = this.head;
    while(current !== null && current.elem !== val){
        current = current.next;
    }
    return current;
}

SLinkedlist.prototype.insert = function(newVal, val){
    var current = this.find(val);
    var newNode = new Node(newVal);
    newNode.next = current.next;
    current.next = newNode;
}
function reverseLinkedList(list, previous){

      //We need to use the the current setting of
      //list.next before we change it. We could save it in a temp variable,
      //or, we could call reverseLinkedList recursively
      console.log(list);
      if(list !== null && list.next !==null){
        reverseLinkedList(list.next, list);
      }
      console.log("after recursion!")
      console.log(list);      
      //Everything after 'list' is now reversed, so we don't need list.next anymore.
      //We passed previous in as an argument, so we can go ahead and set next to that.
      list.next = previous;
     }
reverseLinkedList(list.head, null);

Can anyone help me?

I am trying to reverse linkedlist recursively in Javascript. I have tried myself and search the net to find it. But no success. Below is the code I tried:

var Node = (function(){
    function Node(val){
        this.elem = val;
        this.next = null;
    }
    return Node;
})();

var SLinkedlist = (function(){
    function SLinkedlist(){
        this.head = new Node("head");
    }
    return SLinkedlist;
})();

SLinkedlist.prototype.find = function(val){
    var current = this.head;
    while(current !== null && current.elem !== val){
        current = current.next;
    }
    return current;
}

SLinkedlist.prototype.insert = function(newVal, val){
    var current = this.find(val);
    var newNode = new Node(newVal);
    newNode.next = current.next;
    current.next = newNode;
}
function reverseLinkedList(list, previous){

      //We need to use the the current setting of
      //list.next before we change it. We could save it in a temp variable,
      //or, we could call reverseLinkedList recursively
      console.log(list);
      if(list !== null && list.next !==null){
        reverseLinkedList(list.next, list);
      }
      console.log("after recursion!")
      console.log(list);      
      //Everything after 'list' is now reversed, so we don't need list.next anymore.
      //We passed previous in as an argument, so we can go ahead and set next to that.
      list.next = previous;
     }
reverseLinkedList(list.head, null);

Can anyone help me?

• javascript
• recursion
• data-structures
• linked-list

Share Improve this question Follow edited Jul 9, 2015 at 14:41 bbill 2,30411 gold badge2323 silver badges2828 bronze badges asked Jul 8, 2015 at 20:48 alps07alps07 1922 silver badges66 bronze badges 3

• Any code to show your progress? – Clarkie Commented Jul 8, 2015 at 20:54
• yes! Updated my question with code. Recursive method is taken from some example. – alps07 Commented Jul 8, 2015 at 21:08
• @Arpit- thanks for formatting it. I am new here. – alps07 Commented Jul 8, 2015 at 21:17

Add a ment  | 

6 Answers 6

Sorted by: Reset to default 2

Assuming your list is similar to this:

var list = 
{
  name: "1",
  next: {
    name: "2",
    next: {
      name: "3",
      next: {
        name: "4"
      }
    }
  }
};

console.log("Original list");
var head = list;
while (head != undefined) {
  console.log(head.name);
  head = head.next;
}

which renders

Original list 
1 
2 
3 
4 

You can reverse it with a recursive function like so:

head = reverse(list, undefined);

console.log("Reverse list");
while (head != undefined) {
  console.log(head.name);
  head = head.next;
}


function reverse(list, prev) {
  // if this is the last node, switch it with previous and return
  if (list.next == undefined) {
    list.next = prev;
    return list;
  }

  // otherwise, switch it with the reverse of what is next
  var ret = reverse(list.next, list);
  list.next = prev;
  return ret;
}

which renders

Reverse list 
4 
3 
2 
1 

How does it work? It's based on the principle that:

Reverse([1 2 3 4]) ==   
[ Reverse([2 3 4]) 1 ] ==  
[ Reverse([3 4]) 2 1 ] ==  
[ 4 3 2 1 ]  

Here's my object-oriented recursive solution.

function Node(value) {
    this.value = value;
    this.next = null;
}

function SLinkedList(node) {
    if (node) {
        this.head = node;
    } else {
        this.head = null;
    }
}

SLinkedList.prototype.prepend = function(node) {
    node.next = this.head;
    this.head = node;
}

SLinkedList.prototype.print = function() {
    var arr = [];
    var current = this.head;
    while (current !== null) {
        arr.push(current.value);
        current = current.next;
    }
    alert(arr.join(' '));
}

SLinkedList.prototype.reverse = function() {
    if (this.head === null || this.head.next === null) {
        return;
    }
    var first = this.head;
    var rest = new SLinkedList(this.head.next);
    rest.reverse();
    first.next.next = first;
    first.next = null;
    this.head = rest.head;
}

var list = new SLinkedList();
list.prepend(new Node(4));
list.prepend(new Node(3));
list.prepend(new Node(2));
list.prepend(new Node(1));
list.print();

list.reverse();
list.print();

JSFiddle: http://jsfiddle/5c9gtstk/1/

A few tips for your code, that aren't 100% wrong but I think will help, mostly for brushing up on your linked list:

• it's not typical to have a first node with "head" as the value, though you can do it - just start with your "head" node's next.
• the console.log(list) lines don't tell too much about what's happening because the data structure only contains an elem and next, which is why I wrote a print function. That can help you debug.
• your insert function is also atypical but that's not really an issue in this algorithm :)

http://www.thatjsdude./interview/linkedList.html#singlyLinkedList has a simple, concise explanation of how you can do it.

As for your reverse algorithm, you almost have the correct idea. The main tip I can give here is to draw out what's happening in your recursive calls! Execute your code step-by-step by hand, slowly. It'll take a few seconds but make everything 100% clear.

Specifically, is list.next = previous; all you need to do after reversing the rest of the list? There are a few other pointers you'll need to change.

Others, including an answer here, have given a better explanation than I can give. Again, diagrams are key. http://www.geeksforgeeks/write-a-function-to-reverse-the-nodes-of-a-linked-list/ has a good, short explanation - skip to the part about the recursive method.

The 2 links I have above are 1 browser page each. I encourage you to take a look.

To reverse a linked list, we can use simple recursion method. Pass the head of linked list to the below method.

reverse( head ) {
    if( head ) {
        reverse( head.next );
        console.log( head.data );
    }
}

Complete working solution here

To add to the above answers, here's a LIFO (last in, first out) linked list implementation in ES6/JavaScript, with a function to reverse the list both recursively and in-place (without creating a new List):

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

class List {
  constructor(arr) {
    this.head = null;
    if (arr) {
      arr.forEach(el => this.add(new Element(el)));
    }
  }

  get length() {
    return this.head ? this.countElements(1, this.head) : 0;
  }

  add(el) {
    const element = el;
    element.next = this.head;
    this.head = element;
  }

  countElements(count, element) {
    return element.next ? this.countElements(count + 1, element.next) : count;
  }

  toArray(arr = [], element = this.head) {
    arr.push(element.value);
    return element && element.next ? this.toArray(arr, element.next) : arr;
  }
  
  reverse(prev = null) {
    if (this.head.next) {
      const current = this.head;
      this.head = this.head.next;
      current.next = prev;
      return this.reverse(current);
    }
    this.head.next = prev;
    return this;
  }
}

const list = new List([1, 2, 3, 4, 5, 6, 7 , 8 ,9 , 10]);
console.log(list.toArray().toString());  // returns LIFO list as array (last list el = first array el)
console.log(list.reverse().toArray().toString()); // returns LIFO list reversed as array(first first)

These two existing answers offer great solutions to the problem, but I thought it might be helpful to know why your code isn't working. In javascript, when a recursive call executes, a new closure is created with its own scope. So in the final call, the one where the "tail" is located, the list variable that refers to it is actually a local variable which has overwritten the existing list in the environment. Consequently, when the function exits, reference to this local list is lost if it is not returned.

What the other two answers do is to return that value and store it in a temp variable (the ments in your code are actually not helpful.. you need to store the tail somewhere or you will lose it!)

As you may know, you are not polluting the global scope if all this is handled inside your reverse function.

Also @bbill is absolutely right about executing the code by hand, one step at a time in something like Chrome devtools. This can really offer great insight into what's happening.

Hope this helps.

You can try this method: I took reference from here: https://www.youtube./watch?v=KYH83T4q6Vs Basically, once we reach last node recursively, we then change the pointer from the last node to point it to the prev node.

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }

    reverseLLRec(node) {
        if (!node.next) {
            this.head = node;
            return;
        }
        this.reverseLLRec(node.next);
        const curr = node.next;
        curr.next = node;
        node.next = null;
    }
}

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}
class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }

    reverseLLRec(node) {
        if (!node.next) {
            this.head = node;
            return;
        }
        this.reverseLLRec(node.next);
        const curr = node.next;
        curr.next = node;
        node.next = null;
    }

    insertAtLast(data) {
        const node = new Node(data);
        if (this.head === null) {
            this.head = node;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = node;
        }
    }

    printList() {
        let curr = this.head;
        let list = [];
        while (curr) {
            list.push(curr.val);
            curr = curr.next;
        }
        console.log(list);
    }
}

const ll = new LinkedList();
ll.insertAtLast(1);
ll.insertAtLast(2);
ll.insertAtLast(3);
ll.insertAtLast(4);
ll.insertAtLast(5);
console.log('Before reverse:');
ll.printList();
ll.reverseLLRec(ll.head);
console.log('After reverse:');
ll.printList();