Reversal of singly linked list in JavaScript

Question

I have already implemented reversal of link list in javascript. Can somebody tell optimized way of doing it?I want to do it by less code.

Here I am providing the code:

var tempItem;
var finalLastNode;

function reverseLL(ll) {
  var currentObj = ll,
    prevItem, lastItem, currentTempObj;
  currentTempObj = tempItem;
  if (!currentObj) {
    console.log("No change")
  } else {
    while (currentObj.next) {
      prevItem = currentObj;
      currentObj = currentObj.next;
      lastItem = currentObj;
    }
    if (lastItem) {
      if (!tempItem) {
        tempItem = lastItem;
      } else {
        while (currentTempObj.next) {
          currentTempObj = currentTempObj.next;
        }
        if (tempItem && !tempItem.next) {
          tempItem.next = lastItem;
          finalLastNode = ll;
        } else {
          currentTempObj.next = lastItem;
        }
      }
      prevItem && (prevItem.next = null)
      reverseLL(ll);
    } else {
      while (currentTempObj.next) {
        currentTempObj = currentTempObj.next;
      }
      currentTempObj.next = finalLastNode;
    }
  }
  console.log(tempItem);
}
reverseLL(ll1)

Answer 1

"I want to do it by less code."

It's relatively easy: you keep another variable that denotes the head of the new list. Then, you remove the head node of the input list and make it a new head node of the new list being constructed:

function reverse(head) {
    new_head = head;
    old_head = head.next;
    new_head.next = null; // Terminate cycle.
    while (old_head) {
        current = old_head;
        old_head = old_head.next;
        current.next = new_head;
        new_head = current;
    }
    return new_head;
}

Usage

function node(val) {
    this.val = val;
    this.next = null;
}

a = new node(1);
b = new node(2);
c = new node(3);

a.next = b; b.next = c;
a = reverse(a); // Don't forget to store the new head node.

Hope that helps.

Answer 2

If it's a singly linked list, then I don't see the need for any complex transformation logic, as a node can only have a next node.

So, you could theoretically do it like:

• add all items into an array
• reverse the array
• rebuild the list

Could be i am missing something, but the easiest I came up with, was the following:

function toArray(ll) {
  let arr = [ll];
  while (ll.next) {
    arr.push(ll.next);
    ll = ll.next;
  }
  return arr;
};

function fromArray(arr) {
  let ll = arr[0], i;
  for (i = 1; i < arr.length; i++) {
    ll.next = arr[i];
    ll = ll.next;
  }
  // last has to be set to null, or the thing breaks :)
  ll.next = null;
  return arr[0];
}

function reverseLl(ll) {
  if (!ll) {
    return null;
  }
  return fromArray(toArray(ll).reverse());
};

let l = {
  name: 'parent',
  next: {
    name: 'firstchild',
    next: {
      name: 'secondchild',
      next: {
        name: 'lastchild'
      }
    }
  }
};

// test
console.log(reverseLl(l));

Ofcourse, as Vogel612 metnioned in the comments, this is not the most optimized way. I just presented it as a way that it contains less code, and that it is separated in single utility functions. The code from coderodde is ofcourse lots better.

Instead of deleting my answer, I will simply add 1 more version how you could do it by using ES6 and classes

class SingleNode {
  constructor( data, next = null ) {
    this._data = data;
    this.next = next;
  }
  get data() {
    return this._data;
  }
  get next() {
    return this._next;
  }
  set next( value ) {
    if (value !== null && !(value instanceof SingleNode)) {
      throw 'AssignmentException: value should be of type `SingleNode` or null';
    }
    this._next = value;
  }
  isLast() {
    return (this.next === null);
  }
  setNext( data, next = null ) {
    if (data instanceof SingleNode) {
      this.next = data;
      return;
    }
    this.next = new SingleNode(data, next);
    return this.next;
  }
  static setAndReturnNext( node, nextNode ) {
    node.next = nextNode;
    return nextNode;
  }
  static reverse( singleNode ) {
    if (!singleNode) {
      return null;
    }
    let result = singleNode;
    let newHead = new SingleNode( result.data );
    while (!result.isLast()) {
      result = result.next;
      newHead = new SingleNode( result.data, newHead );
    } 
    return newHead;
  }
}

let node = new SingleNode('parent');
// add some next nodes, fluidic syntax so after each setNext, the new node is returned
node
  .setNext('firstchild')
  .setNext('secondchild')
  .setNext('lastchild');

// create singleNode
let newNode = SingleNode.reverse( node );

// new node is not the same as the old node
console.log( node );
console.log( newNode );

Answer 3

Though much the same as the first answer this is a little more minimalistic.

Note that there is no need to specify undefined (or null). The terminator is added by default in the function entry Also there is only one top variable thus no need to set the new top after the reverse function, as the top is used to move the items up the list and ends up at the top automatically.

Also you can collapse two lines to one as you already have top you just need its next thus top = oldTop.next; oldTop.next = top.next; can be shortened to oldTop.next = (top = oldTop.next).next;

"use strict";
function linkedList() {
  var top, next;
  const entry = (item, next) => ({item, next});
  return {
    add(item) {
      if (!top) { next = top = entry(item) }
      else { next = next.next = entry(item) }
      return this;
    },
    show() {
      next = top;
      while (next) {
        console.log(next.item);
        next = next.next;
      }
      return this;
    },
    reverse() {
      var current, oldTop;
      current = oldTop = top;
      while (oldTop.next) {
        oldTop.next = (top = oldTop.next).next;
        top.next = current;
        current = top;
      }
      return this;
    },
  }
}

linkedList()
  .add("A").add("B").add("C").add("D").add("E").add("F").add("G").add("Last")
  .show()
  .reverse()
  .show()