3 ms·
JavaScript developer, can you reverse a linked list?
- deleted 14y ago[deleted]
- icoder 14y ago// 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 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 http://jsbin.com/ugojoq/67/edit TIL :) [/EDIT]
- vail130 14y agoLinear complexity FTW. Good find. A true developer wouldn't write something they didn't have to.
- hqm42 14y agoLinkedList.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 14y agoLinkedList.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 14y ago[deleted]
- sturob 14y agoLinkedList.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 14y agoNever wrote javascript before. http://jsbin.com/ugojoq/267/edit 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; };