Arunav Goswami
Web Development Consultant at almaBetter
12 mins
2367
A linked list is a technique to store a list of things, like a todo list, where each item has a reference to the next item in the list. It's like a chain, where each link points to the next link. You can add or remove items easily by changing the links between them. In technical terms, A linked list is a data structure used for storing a sequence of elements. It consists of a sequence of nodes, each containing some data and a reference to the next node in the list.
Reversing a linked list means changing the order of the elements in the list so that the last element becomes the first, the secondtolast becomes the second, and so on. This is usually done by updating the references in each node to point to the previous node instead of the next one, effectively reversing the direction of the list.
There was a little girl named Alice who enjoyed playing with her toy trains. She had an extensive track set up in her room that snaked around her bed, bookshelf, and beloved armchair. One day, she decided to arrange her trains on the track in a specific sequence: first, the red train, then the blue, the green, and finally, the yellow train.
Alice was content with her trains' arrangement, but her younger brother Bob entered her room and wanted to play with the trains as well. Unlike Alice, Bob was not very orderly, and he chose to play with the trains by haphazardly pushing them along the track. When he finished, the trains' order was completely different from Alice's initial setup.
Unhappy with the new arrangement, Alice resolved to reverse the order. She placed the yellow train at the front of the track, followed by the green, the blue, and lastly, the red train. The trains were now in the precise order she desired.
Similarly, we can reverse a linked list's order, much like Alice did with her trains. A linked list can be compared to a train track, where each train car represents a node in the list and contains a reference to the subsequent car. To reverse the list, we need to alter the next reference of each node to point to the preceding node instead of the following one. This is akin to positioning the last train car at the track's beginning, succeeded by the secondtolast car, and so forth.
Iterative solutions use loops and conditionals to repeatedly execute a block of code until a condition is met. Iterative solutions are often more efficient in terms of memory usage and execution time since they don't require the overhead of function calls and maintaining a call stack.
Let's say we have the following linked list:
1 > 2 > 3 > 4 > NULL
Initially, we have three pointers:
prev = NULL
current = 1
next = NULL
We start by reversing the first node in the list:
prev = NULL
current = 1 > 2 > 3 > 4 > NULL
next = 2 > 3 > 4 > NULL
1 > NULL
2 > 3 > 4 > NULL
We then move the prev, current, and next pointers to the next node:
prev = 1
current = 2 > 3 > 4 > NULL
next = 3 > 4 > NULL
1 > NULL
2 < 3 > 4 > NULL
We repeat this process for each node in the list until we reach the end:
prev = 2
current = 3 > 4 > NULL
next = 4 > NULL
1 > NULL
2 < 3 < 4 > NULL
prev = 3
current = 4 > NULL
next = NULL
1 > NULL
2 < 3 < 4 < NULL
prev = 3
current = 4 > NULL
next = NULL
1 > NULL
2 < 3 < 4 < NULL
At this point, the list has been fully reversed. We update the head pointer to the last node, which is 4, and return it.
A complete code to reverse the linked list iteratively would be:
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
function reverseList(head) {
let prev = null;
let current = head;
let next_node = null;
while (current) {
next_node = current.next;
current.next = prev;
prev = current;
current = next_node;
}
return prev;
}
Common challenges or errors that can arise:
Recursion is a programming technique where a function calls itself with different arguments until a certain condition is met. Recursion allows you to solve complex problems by breaking them down into smaller, simpler subproblems that can be solved recursively.
To reverse a linked list recursively, we need to define a recursive function that takes the head of the linked list as input and returns the new head of the reversed linked list.
Suppose we have the following linked list:
1 > 2 > 3 > 4 > 5
We first define a recursive function reverseList that takes the head of the linked list as an argument:
In this example, the head of the linked list is the node with value 1.
We check if the head of the linked list is either None or the last node in the linked list (i.e., if it doesn't have a next node). If so, we simply return the head as is:
In this example, the head has a next node (i.e., it's not the last node in the linked list), so we proceed with the recursive call.
We make a recursive call to reverseList with the next node as the new head:
let newHead = reverseList(head.next);
This will recursively reverse the rest of the linked list and return the new head, which in this example is the node with value 5.
We then set head.next.next to head to reverse the order of the nodes:
head.next.next = head
At this point, the linked list looks like this:
1 < 2 < 3 < 4 < 5
We then set head.next to None to sever the original link between head and its next node:
head.next = null
At this point, the linked list looks like this:
1 < 2 < 3 < 4 < 5
^

None
We finally return the new head of the reversed linked list, which is the node that was originally the last node in the linked list (i.e., the node that was returned by the last recursive call):
return new_head
The final reversed linked list looks like this:
5 > 4 > 3 > 2 > 1
So the complete code to reverse the linked list recursively would be:
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
function reverseList(head) {
if (!head  !head.next) {
return head;
}
let newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
Reversing a linked list through a recursive approach can present some difficulties and common pitfalls. Here are a few to be aware of:
Deciding whether to use a recursive or iterative approach for reversing a linked list depends on the specific context and requirements. Here are some factors to keep in mind:
In general, if efficiency is a key concern, an iterative approach might be more suitable. However, if the clarity is of greater importance or the problem is inherently recursive, a recursive approach might be the better option.
In conclusion, reversing a linked list is a way of changing the order of elements in the list so that the last becomes the first, the secondtolast becomes the second, and so on. This is typically done by updating the references in each node to point to the previous node instead of the next one. Iterative solutions use loops and conditionals to execute a block of code repeatedly until a condition is met. They are often more efficient in terms of memory usage and execution time than recursive solutions. Reversing a linked list can be useful in various situations, such as pagination, text editing, routing tables, and audio and video processing.
Some best practices to keep in mind while reversing a linked list:
1. Can you explain the time and space complexity of your iterative linked list reversal algorithm?
Answer: The time complexity of an iterative linked list reversal algorithm is O(n), where n is the number of nodes in the list. The space complexity is O(1), because the algorithm only uses a constant amount of additional memory for the threepointers.
2. Can you explain the time and space complexity of your recursive linked list reversal algorithm?
Answer: The time complexity of a recursive linked list reversal algorithm is also O(n), where n is the number of nodes in the list. The space complexity is O(n) because the algorithm uses additional memory for the recursive function call stack.
3. How would you handle edge cases such as empty or singlenode lists when reversing a linked list?
Answer: When reversing a linked list, it's important to handle edge cases such as empty or singlenode lists. For example, you might define a base case to return the head pointer if the list is empty or if it contains only one node.