Last active
November 6, 2019 11:28
Star
You must be signed in to star a gist
Reverse a Linked List in JavaScript.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Definition for singly-linked list. | |
* function ListNode(val) { | |
* this.val = val; | |
* this.next = null; | |
* } | |
*/ | |
/** | |
* @param {ListNode} head | |
* @return {ListNode} | |
*/ | |
/* Iterative */ | |
var reverseList = function(head) { | |
var result = null; | |
var stack = []; | |
var current = head; | |
while (current) { | |
stack.push(current); | |
current = current.next; | |
} | |
// Set head to end of list. | |
result = stack.pop() || []; | |
current = result; | |
while (current) { | |
current.next = stack.pop(); | |
current = current.next; | |
} | |
return result; | |
}; | |
/* Recursive */ | |
var reverseListRecursive = function(node, parent) { | |
var result = parent || {}; | |
if (node) { | |
var child = node.next; | |
node.next = parent; | |
result = reverseListRecursive(child, node); | |
} | |
return result; | |
} |
More short recursive reverser
reversePrint = (L, LInv) => L === null ? LInv
: reversePrint(L.next, Object.assign(L, {next: LInv || null}));
//(For such structure, with change of itself: )
var someList = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: {
value: 4,
next: null
}
}
}
};
// use as someList = reversePrint(someList );
function LinkedList() {
this.head = null;
}
function ListNode(val) {
this.val = val;
this.next = null;
}
LinkedList.prototype.reverse = function() {
var curr = this.head;
var next = null;
var prev = null;
while(curr) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
this.head = prev;
}
var myLL = new LinkedList();
myLL.add(10);
myLL.add(30);
myLL.add(50);
myLL.reverse();
console.log(myLL);
const reverseLinkedList = (node, newChildOldParent=null ) => {
if( node.next ){
reverseLinkedList(node.next, node);
}
node.next = newChildOldParent;
return node;
}
reverseLinkedList( listHead )
Your solution is not correct. The problem is that you are reversing the list alright, but you are getting the first element again in the end (as the stack unfolds). Your first element is now the last and doesn't have a next node.
This is the corrected version:
const reverseLinkedList = (curr, prev) => {
if (curr.next) {
const newHead = reverseLinkedList(curr.next, curr);
curr.next = prev;
return newHead; // pass the new head up the list
}
curr.next = prev;
return curr; // base case; return the tail
};
You can test it using the following LL
const someList = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: {
value: 4,
next: null
}
}
}
};
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This was really helpful!