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

Answer 5

Reversing the SinglyLinkedList: Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

To understand The Solution we have to keep track of previous head and next variables for example in above input Head = 1 ; next = 2 we don't have previous so assume previous = null loop the list till head is not null. reverse the connections(previous and next) of head. Below is the code

var reverseList = function(head) {
    let previous = null;
    while(head !== null){
        let next = head.next;
        head.next = previous;
        previous= head
        head = next;
    }
    return previous;
    
};

Answer 6

//O(n) | O(1) wherre n is the number of nodes in the linked list

class Node{
  constructor(val){
    this.val = val;
    this.next = null;
  }
}


function reverseLinkedList(head) {

 if(!head) return null;
 
 let p1 = head;
 let p2 = null;
	
	while(p1){
		let temp = p1.next;
		p1.next = p2;
		p2 = p1;
		p1 = temp;
	}
	
	return p2;
}


const a = new Node(1);
a.next = new Node(2);
a.next.next = new Node(3)

console.log("Current Node",a);
console.log("Reversed List",reverseLinkedList(a))

Answer 7

class LinkedList {
    constructor () {
        this.head = this.tail = null
    }

    // add to the end of the list
    append (value) {
        if (!this.tail) {
            this.head = this.tail = new Node(value)
        } else {
            let oldTail = this.head
            this.head = new Node(value)
            this.head.next = oldhead
        }
    }

    reverseList() {
        //your code here
        let currentNode = this.head
        this.head = null
        while(currentNode) {
            if (!this.head) {
                this.head = new Node(currenthead.data)
            } else {
                let oldhead = this.head
                this.head = new Node(currentNode.data)
                this.head.next = oldhead
            }
            currentNode = currentNode.next
        }
    }
}

class Node {
    constructor (value, next) {
        this.data = value
        this.next = next || null
    }
}

const list = new LinkedList()
list.append(1)
list.append(2)
list.reverseList()

Answer 8

Since inserting data at the beginning of the linked list pushes other first nodes till the end, and since it's a O(1) process. Then I created the following function reverse() where it basically insert node elements in the beginning which basically will get a reversed list at the end.

Here's a demo down below:

class Node {
    constructor(data, next = null) {
        this.data = data;
        this.next = next;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
    
    insertFirst(data = null) {
        // make new head point to the previous head
        this.head = new Node(data, this.head);
        this.size ++;
    }
    
    insertLast(data = null) { // insert last in the beginning will be the first in the linked list
        const node = new Node(data);
        // If empty, insert first
        if (!this.head) this.insertFirst(data);
        else {
            let current = this.head;
            // while next is not null, continue
            while (current.next) 
                current = current.next;
            // eventually next is null, we want to set next here to the node we want to add
            current.next = node;
        }
        this.size ++;
    }
    
    // print linked list
    print() {
        let current = this.head;
        let output = "";
        while (current) { // while current is not null, eventually it will be null
            output += current.data + " => ";
            current = current.next; // current jumping to the next node
        }
        output += "| NULL"; // ending
        console.log(output);
        return output;
    }
    
    reverse() {
        if (!this.head) return; // if no head, do nothing
        let current = this.head;
        const linkedList = new LinkedList(); // create a new linked list
        // don't worry, it will be garbage collected once this function ends since it's not a global variable
        while (current) { 
            linkedList.insertFirst(current.data); // insert first at the beginning will be the end of the linked list at the end
            current = current.next;
        }
        // assign current head to the reversed linked list head
        this.head = linkedList.head;
    }
}

const linkedList = new LinkedList();
// fill data as 100 -> 200 -> 300 -> 400
linkedList.insertLast(100);
linkedList.insertLast(200);
linkedList.insertLast(300);
linkedList.insertLast(400);

// To view results
const bodyElement = document.getElementsByTagName("body")[0];
bodyElement.innerHTML = `<p>Original Linked List: <b>${linkedList.print()}</b></p>`; // 100 200 300 400
linkedList.reverse();
bodyElement.innerHTML += `<p>Reversed Linked List: <b>${linkedList.print()}</b></p>`; // 400 300 200 100

b {
  color: green;
}

<body></body>

Overall, the whole process of this reverse() function is O(n).

Hopefully this sounds clear to you, and correct me if I'm wrong.

Answer 9

This is my recursive solution: https://codesandbox.io/s/reverse-linked-list-tqh2tq?file=/src/index.js

let d = { me: "d" };
let c = { me: "c", next: d };
let b = { me: "b", next: c };
let a = { me: "a", next: b };

const reverseMe = (o) => {
  let lastDude;

  if (o.next.next) lastDude = reverseMe(o.next);
  else lastDude = o.next;

  o.next.next = o;
  o.next = null;
  return lastDude;
};

console.log("result", reverseMe(a));