Revisions to Reversal of singly linked list in JavaScript

added 2153 characters in body

Source Link

edited Aug 23, 2017 at 13:38

825
10
25

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

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

deleted 9 characters in body

Source Link

edited Aug 22, 2017 at 15:02

Icepickle

825
10
25

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:

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

constfunction 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];
}

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

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:

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

const 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];
}

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

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

Source Link

created Aug 22, 2017 at 9:51

Icepickle

825
10
25

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:

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

const 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];
}

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

Stack Exchange Network

Return to Answer