Skip to content

Instantly share code, notes, and snippets.

@primaryobjects
Last active November 6, 2019 11:28
  • Star 10 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save primaryobjects/0eec899de44fbe19770a225ddac81b82 to your computer and use it in GitHub Desktop.
Reverse a Linked List in JavaScript.
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
/* Iterative */
var reverseList = function(head) {
var result = null;
var stack = [];
var current = head;
while (current) {
stack.push(current);
current = current.next;
}
// Set head to end of list.
result = stack.pop() || [];
current = result;
while (current) {
current.next = stack.pop();
current = current.next;
}
return result;
};
/* Recursive */
var reverseListRecursive = function(node, parent) {
var result = parent || {};
if (node) {
var child = node.next;
node.next = parent;
result = reverseListRecursive(child, node);
}
return result;
}
@PantherHawk
Copy link

This was really helpful!

@spmbt
Copy link

spmbt commented Apr 10, 2018

More short recursive reverser

reversePrint = (L, LInv) => L === null ? LInv
    : reversePrint(L.next, Object.assign(L, {next: LInv || null}));

//(For such structure, with change of itself: )
var someList = {
   value: 1,
   next: {
      value: 2,
      next: {
         value: 3,
         next: {
            value: 4,
            next: null
            }
         }
    }
};
// use as someList = reversePrint(someList );

@hozefaj
Copy link

hozefaj commented Apr 15, 2018

function LinkedList() {
  this.head = null;
} 
 
function ListNode(val) {
  this.val = val;
  this.next = null;
}

LinkedList.prototype.reverse = function() {
  var curr = this.head;
  var next = null;
  var prev = null;
  
  while(curr) {
    next = curr.next;
    
    curr.next = prev;
    
    prev = curr;
  
    curr = next;
  }
  this.head = prev;
}

var myLL = new LinkedList();
myLL.add(10);
myLL.add(30);
myLL.add(50);
myLL.reverse();
console.log(myLL);

@r-i-c-h
Copy link

r-i-c-h commented Jul 15, 2018

const reverseLinkedList = (node, newChildOldParent=null ) => {
    if( node.next ){
        reverseLinkedList(node.next, node);
    }
    node.next = newChildOldParent;
    return node;
}
reverseLinkedList( listHead )

@rupeshdabbir
Copy link

@r-i-c-h:

Your solution is not correct. The problem is that you are reversing the list alright, but you are getting the first element again in the end (as the stack unfolds). Your first element is now the last and doesn't have a next node.

This is the corrected version:

const reverseLinkedList = (curr, prev) => {
    if (curr.next) {
        const newHead = reverseLinkedList(curr.next, curr);
        curr.next = prev;
        return newHead; // pass the new head up the list
    }
    
    curr.next = prev;
    return curr; // base case; return the tail
};

You can test it using the following LL

const someList = {
    value: 1,
    next: {
        value: 2,
        next: {
            value: 3,
            next: {
                value: 4,
                next: null
            }
        }
    }
};

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment