strategies to reverse a linked list in JavaScript

Question

I just struggled through a simple interview question: Please reverse a singly linked list.

While I failed to provide a working answer in time to save the interview, I was able to come up with a solution afterwards.

Is my solution correct? How would you analyze this with Big-Oh? Are there more efficient ways to reverse a singly linked list?

// reverse a linked list

var reverseLinkedList = function(linkedlist) {
  var node = linkedlist;
  var previous = null;

  while(node) {
    // reverse pointer
    node.next = previous;
    // increment previous to current node
    previous = node;
    // increment node to next node
    if (node.next){
      node = node.next
    } else {
      node = null;
    }
  }
}

Note: In my search for similar posts, I did find one example in JavaScript. I was wondering if my code is possible (without a temp variable). Thank you.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

ES6 solution: Just keep a track of the reversed list and keep adding that to tmp.

const reverseLinkedList = (head) => {
  let reversed = null;
  while(head) {
    const tmp = head;
    head = head.next;
    tmp.next = reversed;
    reversed = tmp;
  }

  return reversed;
};

console.log(JSON.stringify(reverseLinkedList({
  data: 1,
  next: {
    data: 2,
    next: {
      data: 3,
      next: {
        data: 4,
        next: {
          data: 5,
          next: {
            data: 5,
            next: {
              data: 6
            }
          }
        }
      }
    }
  }
})));