strategies to reverse a linked list in JavaScript

There are a couple of problems with your code. This should make it clear.

// reverse a linked list  
var reverseLinkedList = function(linkedlist) {
  var node = linkedlist;
  var previous = null;

  while(node) {
    // save next or you lose it!!!
    var save = node.next;
    // reverse pointer
    node.next = previous;
    // increment previous to current node
    previous = node;
    // increment node to next node or null at end of list
    node = save;
  }
  return previous;   // Change the list head !!!
}
linkedlist = reverseLinkedList(linkedlist);

This would be O(n) in time, since you do a constant number of operations on each node. Conceptually, there isn't a more efficient way of doing things (in terms of big-O notation, there's some code optimization that could be done.)

The reason why you can't exceed O(n) is because, in order to do so, you would need to skip some nodes. Since you need to modify each node, this wouldn't be possible.

Efficiency then comes down to a constant factor. The fewer operations you can do per item in the list, the faster your code will execute.

I'd implement like this:

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
  if(list.next !== null){
    reverseLinkedList(list.next, 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, null);

Of course, this is recursive, so it would be inefficient in terms of space, but I like recursive code :)

This also doesn't return the reversed linked list, but we could fairly easily modify things to do so if that were important.


You could solve this problem recursively in O(n) time as ckersch mentions. The thing is, that you need to know that recursion is memory intensive since functions accumulate in the calls stack until they hit the stop condition and start returning actual things.

The way I'd solve this problem is:

 const reverse = (head) => {
   if (!head || !head.next) {
     return head;
   }
   let temp = reverse(head.next);
   head.next.next = head;
   head.next = undefined;
   return temp;
 }    

When reverse() reaches the end of the list, it will grab the last node as the new head and reference each node backwards.