HN Explorer

8 comments

[ 3.5 ms ] story [ 21.7 ms ] thread
[deleted]
(comment deleted)
icoder
// This solution stores the reverse order in the nodes themselves. It's hacky so I like it :)

LinkedList.prototype.reverse = function () { var q;

  // Make doubly linked
  for (q = this.head; q; q = q.next ) {
    if ( q.next ) q.next.prev = q; else this.head = q;
  }

  // Reverse  
  for (q = this.head; q; q = q.prev ) {
    q.next = q.prev;
  }
  
  // Better clean up
  for (q = this.head; q; q = q.next ) {
    q.prev = undefined;
  }
};

http://jsbin.com/ugojoq/43/edit

[EDIT]

Ah, I didn't know, but it possible to reverse a singly linked list without remembering the entire list:

  var p = this.head, q, r;
  while ( p ) {
    r = q;
    q = p;
    p = p.next;
    q.next = r;
  }
  this.head = q;
(blatantly based on an answer found on StackOverflow).

http://jsbin.com/ugojoq/67/edit

TIL :) [/EDIT]

vail130
Linear complexity FTW. Good find. A true developer wouldn't write something they didn't have to.
hqm42 

  LinkedList.prototype.reverse = function () {
    var rev = function(e,tail) {
      if (!e) {
        return tail;
      } else {
        var next = e.next;
        e.next = tail;
        return rev(next, e);
      }
    };
    this.head = rev(this.head, null);
  };
zx2c4 

    LinkedList.prototype.reverse = function () {
      var next, head = null;
      while (this.head !== null) {
        next = this.head.next;
        this.head.next = head;
        head = this.head;
        this.head = next;
      }
      this.head = head;
    };
[deleted]
(comment deleted)
sturob 

  LinkedList.prototype.reverse = function () {
    var tail = function(prev, current){
      if (current.next) {
        tail(current, current.next);
      } else {
        this.head = current;
      }
      current.next = prev;
    }.bind(this);
  
    tail(null, this.head);
  };
Rockdtben
Never wrote javascript before.

http://jsbin.com/ugojoq/267/edit

LinkedList.prototype.reverse = function () {

  var start = this.head;
  var prev = this.head;
  var curr = prev.next;
  prev.next = null;
  while(curr !== null) {
    var next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  this.head = prev;
};