4
\$\begingroup\$

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)
\$\endgroup\$
1
  • 3
    \$\begingroup\$ Any chance you could provide some test data with it? \$\endgroup\$
    – Icepickle
    Aug 22, 2017 at 9:14

3 Answers 3

4
\$\begingroup\$

"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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
5
  • 1
    \$\begingroup\$ +1 in general, though to use const and unnamed functions where function is plain better ( to resolve stack traces) is bad form IMO. \$\endgroup\$
    – konijn
    Aug 22, 2017 at 13:15
  • 1
    \$\begingroup\$ @konijn You are perfectly right :) I made simple' functions of them :) \$\endgroup\$
    – Icepickle
    Aug 22, 2017 at 15:02
  • \$\begingroup\$ this requires \$O(n)\$ additional space, which is utterly unnecessary \$\endgroup\$
    – Vogel612
    Aug 23, 2017 at 11:27
  • \$\begingroup\$ @Vogel612 That's true, however, I didn't say it was more performant :) The OP just requested less code to write. After I saw the response from coderodde, I also saw that his implementation was lots better \$\endgroup\$
    – Icepickle
    Aug 23, 2017 at 11:43
  • \$\begingroup\$ @Vogel612 I added the remark that the original was not that performant, and added an es6 class to maintain some difference from other answers ;) \$\endgroup\$
    – Icepickle
    Aug 23, 2017 at 13:38
-1
\$\begingroup\$

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

\$\endgroup\$
8
  • \$\begingroup\$ -1, you are sliding into write shorter code instead of better code. Which is too bad, you can clearly write good code. \$\endgroup\$
    – konijn
    Aug 23, 2017 at 0:25
  • \$\begingroup\$ @konijn Please explain why you think this is bad code? IMHO this code is a short and elegant curry puff, not just a slasher motivated by the character cull of the standard algorithm, but a deliberate reduction in complexity. That null in the top answer is the bad code , the very reason I had to post this answer IMHO. \$\endgroup\$
    – Blindman67
    Aug 23, 2017 at 0:46
  • \$\begingroup\$ if (!top) { next = top = entry(item) }, oldTop.next = (top = oldTop.next).next;, are both examples of code that is trying too hard, you will not find a coding standard that will allow for this. \$\endgroup\$
    – konijn
    Aug 23, 2017 at 12:24
  • \$\begingroup\$ @konijn Please take a read of the coding standard I use tc39.github.io/ecma262 The accepted answer will not even parse in a strict environment, has NO variable declaration, bad use of null (one of which demonstrates that the method of reversal is not fully understood), contains redundant code, runs 50% slower than mine, Incorrect use of ;, wrong case for object declaration. So why apply arbitrary rules, or is this just internal nepotism with one standard for this and another for that. My code is way better than the accepted answer, and your -1 is without merit. \$\endgroup\$
    – Blindman67
    Aug 23, 2017 at 15:32
  • \$\begingroup\$ This should be a chat.. 1) Chill out 2a) That is a language spec, not a coding standard 2b) These are coding standards: google.github.io/styleguide/jsguide.html or github.com/airbnb/javascript 3) Try jshint.com before complaining about semicolons in other answers or thinking your code is perfect 4) There is no accepted answer? 5) The top answer's code has indeed flaws 6) I think it would be a quick fix to change the -1 to +1 7) I only give -1 to folks who are either terrible (not you) or who could up their game and become great \$\endgroup\$
    – konijn
    Aug 23, 2017 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.