In this question, we need to reverse a linked list. A linked list is a data structure consisting of nodes that contain a data field and a reference to the next node. The head refers to the following node in its “head’.next” property. The linked list ends when the reference to the next node is null. It looks something like this:
{
value: 4, // this is the head node
next: {
value: 7,
next: {
value: 1, // this is the last node. we know this because it's next reference is null
next: null
}
}
}Which we can visualize as
4 -> 7 -> 1 -> null
If we reverse it, it would look like this:
1 -> 7 -> 4 -> null
But the better way to visualize it is like this:
null <- 4 <- 7 <- 1
Why? Because what we’re actually going to do is not switch the nodes around while keeping the null node in place. Instead, we’re going to add a null node to the left of the linked list and flip the direction of the pointers, which would automatically remove the null node on the right. The steps would look like this:
Step 0: 4 -> 7 -> 1 -> null
Step 1: null 4-> 7 -> 1 -> null
Step 2: null <- 4 7 -> 1 -> null
Step 3: null <- 4 <- 7 1 -> null
Step 4: null <- 4 <- 7 <- 1 null
And in a linked list, if a node is not being referenced (like the null node all the way to the right), it’s not actually in the linked list. So the final result, is really:
null <- 4 <- 7 <- 1
Or viewed another way:
1 -> 7 -> 4 -> null
Now, to the code. We can start with the function skeleton provided by LeetCode.
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
};It is expecting a linked list (called head) and returns another linked list. We know that the returned linked list is supposed to be a reversed form of the linked list that was passed in.
The key to this is to keep track of three different nodes at once: the head node (which is already called head), the node previous to the head (which we’ll call prevNode), and the node after the head node (which we’ll call nextNode).
We’ll use the example above to walk you through the code for the steps.
4 -> 7 -> 1 -> null
This part is very important. We stated it at the beginning of this article, but we’ll state it again here. We know which node the head points to because of a property it has called next. This is denoted “head.next”. At the beginning, head.next points to the next node (the node to the right of the head), but we’ll flip it and make it point to the previous node (the node to the left of the head). The only problem at first is there is no previous node, or to say it another way, no node to the left of the head. That’s why we need to create a new “null” node at the start of the linked list.
null 4 -> 7 -> 1 -> null
This is what that looks like in code.
let prevNode = null;Now we start the loop that will do all the hard work for us. It will keep looping over our linked list until head is pointing to a null reference. The loop skeleton looks like this.
while (head !== null) {
}Ok, so what does the inside of the loop look like? Remember how we said we need to keep track of three things, the head, previous node, and next node? At this point, we already know two of those. Head is the the number 4 and previous is what’s to the left of that, which is null. The third variable is what’s to the right of the head node — the number 7. To clarify, head.next already has a value (7). All we’re doing in this step is capturing that value in a variable we’re calling nextNode.
while (head !== null) {
let nextNode = head.next; // gets a reference to the node to the right of the head
}prevNode: null
head: 4
head.next: 7
nextNode: 7
For reference, remember this is where we are at this point.
null 4 -> 7 -> 1 -> null
Now comes the part where we do our first reversal. Instead of the head (4) pointing to the next node (7), we’ll change it to point to the previous node (null) by reassigning the head.next property to look at the prevNode (null) instead of nextNode.
while (head !== null) {
let nextNode = head.next;
head.next = prevNode; // flip it so that head is pointing to the node to the left of it
}Notice how the arrow is flipped from right to left.
null <- 4 7 -> 1-> null
prevNode: null
head: 4
head.next: null
nextNode: 7
Cool, so we’ve done the reversal. The only thing that’s left to do in this loop is to reassign a couple of variables so that when the next loops start, it’s just as easy to reverse the remaining arrows. We do this by reassigning the previous node to where the head is now.
while (head !== null) {
let nextNode = head.next;
head.next = prevNode;
prevNode = head; // shift the prevNode reference to the right
}prevNode: 4
head: 4
head.next: null
nextNode: 7
And then reassigning the head to the same value as the next node (nextNode).
while (head !== null) {
let nextNode = head.next;
head.next = prevNode;
prevNode = head;
head = nextNode; // shift the head node to the right
}prevNode: 4
head: 7
head.next: 4
nextNode: 7
Now that that iteration of the loop is done, the same steps will happen over and over again until the head is null. To remind you of what the effect of the final loops will be:
null <- 4 <- 7 1 -> null
null <- 4 <- 7 <- 1 null
Since we’ve reached the end of the loop, all that’s left is to return the linked list.
Remember that since head is null
null <- 4 <- 7 <- 1 null
We need to return prevNode instead.
null <- 4 <- 7 <- 1 null
And that’s it! The full implementation is at the bottom of this page, but if you want to support us and are interested in the resources we use to make this content, check out the links below.
AFFILIATE LINKS
Great resource I use to learn algorithms.
40% off Tech Interview Pro: http://techinterviewpro.com/terriblewhiteboard
20% off CoderPro: http://coderpro.com/terriblewhiteboard
Last, but not least, here is the full implementation.
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let prevNode = null;
while (head !== null) {
let nextNode = head.next;
head.next = prevNode;
prevNode = head;
head = nextNode;
}
return prevNode;
};Link to problem on LeetCode: https://leetcode.com/problems/reverse-linked-list/