This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.
You're sent a linked list of numbers, but it's been received in the opposite order to what you need. This has happened multiple times now, so you decide to write an algorithm to reverse the lists as they come in. The list you've received is as follows:
// 17 -> 2 -> 21 -> 6 -> 42 -> 10
Write an algorithm for a method reverseList that takes in a head node as a parameter, and reverses the linked list. It should be capable of reversing a list of any length.
You may use the example linked list for testing purposes. Your method will be called as such:
class LinkedListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
l1 = new LinkedListNode(1);
l1.next = new LinkedListNode(2);
reverseList(l1);
Seems pretty easy, right? To reverse an entire linked list, simply reverse every pointer. If 1 is pointing at 2, flip it so 2 should point to 1.
// 17 -> 2 -> 21 -> 6 -> 42 -> 10
// becomes
// 17 <- 2 <- 21 <- 6 <- 42 <- 10
The actual reversal method is actually pretty straightforward, but be aware that it takes some time to reason out. It's easy to get lost, so make sure you draw lots of diagrams.
As this is a problem (reversing an entire linked list) that can be broken up into sub-problems (reverse the pointer between two nodes), it seems like a good opportunity to use recursion.
There are many ways to do the actual reversal, and we'll cover both an iterative and recursive approach, but the general methodology is as follows:
- Begin by creating 3 pointers:
newHead,headandnextNode.-
newHeadandnextNodeare initialized tonull. -
headstarts off pointing to the head of the linked list.
-
- Iterate (or recursively do) through the following process until
headisnull. This means that the end of the list has been reached:
class LinkedListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
l1 = new LinkedListNode(1);
l2 = new LinkedListNode(2);
l1.next = l2;
// we start at head
let head = l1;
let newHead = null;
while (head != null) {
// store the node to the right to reuse later
let nextNode = head.next;
// set the current node's next to point backwards
head.next = newHead;
// store the current node, to be used as the new next later
newHead = head;
// the previously right-side node is now processed
head = nextNode;
}
console.log(l2);
It's difficult to visualize this chain of events, so let's use comments to visualize it. During the interview, try not to keep it in your head.
It'll be especially difficult while balancing your nerves and talking to the interviewer. Take advantage of the whiteboard not just to record things, but also to think through potential steps.
Let's walk through it step by step and then look at working code. Let's reverse an extremely basic list, like 8 -> 4. The first line is let nextNode = head.next;, which will store the node to the right.
nextNode = 4
// 8 -> 4
Then we'll do head.next = newHead;, which will set the current node's next to point backwards.
nextNode = 4
// <- 8, 4
Now newHead = head; will store the current node, to be used as the new next later.
newHead = 8
nextNode = 4
// <- 8, 4
Finally, the previously right-side node is now processed:
newHead = 8
nextNode = 4
// <- 8, 4
^
current node
Now we process the next one with the same steps. nextNode = head.next; will store the node to the right.
newHead = 8
nextNode = null
// <- 8, 4
^
current node
Again, set the current node's next to point backwards with head.next = newHead;. Recall that newHead is 8! This is where we make the switch:
newHead = 8
nextNode = null
// <- 8 <- 4
^
current node
Now let's see this all put together in code, with lots of comments for edification!
class LinkedListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
l1 = new LinkedListNode(8);
l2 = new LinkedListNode(4);
l1.next = l2;
// start at head, 8
let head = l1;
// example: 8 -> 4
let newHead = null;
while (head) {
/* FIRST PASS */
// store the node to the right
let nextNode = head.next;
// nextNode = 4, still 8 -> 4
// set the current node's next to point backwards
head.next = newHead;
// 8 -> null
// store the current node, to be used as the new next later
newHead = head;
// newHead = 8
// the previously right-side node is now processed
head = nextNode;
// head = 4
/* SECOND PASS */
// store the node to the right
nextNode = head.next;
// nextNode = null
// set the current node's next to point backwards
head.next = newHead;
// 4 -> 8
// store the current node as the previous one
newHead = head;
// the previously right-side node is now processed
head = nextNode;
}
console.log(l2);
Does that all make sense? Be sure to go through the iterative approach a few times.
Here's the recursive way to do it. This can also be tricky, especially on first glance, but realize most of the magic happens when it gets to the end.
function reverseList(head) {
if (!head || !head.next) {
return head;
}
let rest = reverseList(head.next);
head.next.next = head;
delete head.next;
return rest;
}
Let's take an easy example of 8 -> 4 again let rest = reverseList(head.next); takes 4 and calls reverseList on it.
Calling reverseList on 4 will have us reach the termination clause because there is no .next:
if (!head || !head.next) {
return head;
}
We go up the stack back to when 8 was being processed. rest now simply points to 4. Now notice what happens:
// remember, head is 8 - it is being processed
// head.next is 4
head.next.next = head;
// head.next.next was null since 4 wasn't pointing to anything
// but now head.next (4) points to 8
And we return 4 - which is pointing to 8. And we can simply extrapolate that to longer linked lists! Note that the recursive approach requires more space because we need to maintain our call stack.
Top comments (1)
What program do you use to create these diagrams?
