This content originally appeared on DEV Community and was authored by Jay Cruz
A common interview question you may come across if you’re applying for Software Engineer positions (especially at large FAANG types of companies) is to reverse a linked list.
If you’re familiar with what linked lists are this problem may seem like a piece of cake. Well not so fast!
Reversing a linked list involves several different steps that need to be implemented in a specific order. So let’s start by going over what linked lists actually are and the types of linked lists you’re most likely to come across in the wild.
What are Linked Lists?
A linked list is a data structure. It’s a collection of elements or nodes stored linearly with each node containing a pointer that references the next node in the list, therefore linking the entire collection of nodes with one another. This is the basic overview of the concept. Now there are several types of linked lists such as singly and doubly-linked lists. Here we’ll just be implementing the first.
Singly-linked lists are a collection of nodes with each node holding a next pointer referencing the following node until the last node's next pointer points to null.
{1, next} => {2, next} => {3, next} => {4, next} => null
Doubly-linked lists are also a collection of nodes though they have a pointer to the next node like singly-linked lists, they also hold a pointer to the previous node.
{prev, 1, next} <=> {prev, 2, next} <=> {prev, 3, next} => null
Iterative Approach
To iteratively reverse a singly linked list, we must adjust the node pointers of each node to point to the previous node in the list. Since a singly linked list only has nodes with next pointers, we need to manually track the previous node before each node we are currently traversing on.
To solve this problem we should be manipulating the node pointers in place and not creating a new linked list.
The following is what our singly linked list nodes will appear as:
Now that we have a visual of what we’ll be working with let’s implement our solution in the reverse() function below.
On lines 5-7 we’re setting several pointers to keep track of the current node, previous node before the current, and next node after current. Then for lines 10–15, we loop to perform our reversal by adjusting the node pointers during each iteration to reverse the linked list in place. When reversal is done we break from the loop. On lines 17–18 we reset the head to be the last node from the original order of the singly linked list and return a reference to the new head.
Before: {1, next} => {2, next} => {3, next} => {4, next} => null
After: {4, next} => {3, next} => {2, next} => {1, next} => null
Recursive Approach
We’ve already seen how we can reverse a list iteratively now let’s go over how to reverse a singly linked list recursively.
We’ll start at the top with the head node to reverse the list then recursively traverse down the call stack until we reach the last node. When we reach the last node, we can then traverse back up the call stack reversing the list by adjusting each node’s next pointer along the way. Once we’re back at the top since we kept a reference to the last node (the new head) we can just return it giving us a completely reversed list.
Line 3–5 is our exit condition for when we’re finished reversing the linked list, we will just return the new head here. Then line 6–9 is the core of our algorithm. Line 6 is where we are moving downwards on the call stack until we arrive at the end of the list. Lines 7 & 8 is where we adjust our next pointers to reverse the links, and line 9 is where we are returning up the call stack with the evaluated result of reversedHead.
The visual below might help with understanding this logic. It represents how the call stack appears for this problem:
-----------------CALL STACK-------------------
-(head)(reversedHead)-------------------------
----------(head)(reversedHead)----------------
-------------------(head)(reversedHead)-------
---------------------------------------(head)-
In the above visual, each line represents a stack frame that is created for each recursive function call. The top reference to the head is when it is first passed into our recursivelyReverseList() function. The last line represents our base case for when we reach the end of the list. Then the reversal happens when returning back up the call stack with a reference to the new head of the list.
Summary
Learning how to reverse a linked list can be a great exercise for learning common interview problems. It may trip you up plenty (like it did me!) but if you keep at it you might gain a better understanding of this fundamental data structure.
Resources
More content at plainenglish.io
This content originally appeared on DEV Community and was authored by Jay Cruz
Jay Cruz | Sciencx (2021-08-19T00:40:34+00:00) Reverse a Singly Linked List in JavaScript (Iteratively and Recursively). Retrieved from https://www.scien.cx/2021/08/19/reverse-a-singly-linked-list-in-javascript-iteratively-and-recursively/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.