Reverse A Singly Linked List - Everything You Need To Know
Updated: Jun 3, 2022
In our previous article we learnt how to find the middle node in a singly linked list. In this article we will discuss how to reverse a given singly linked list.
Problem Statement
Write an algorithm to reverse the given singly linked list.
Examples
Example 1:
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 5 -> 4 -> 3 -> 2 -> 1Example 2:
Input: 2 -> 4 -> 6
Output: 6 -> 4 -> 2Prerequisites
Fundamental understanding of singly linked lists.
Solution 1: Using Stack
We can use the properties of a stack data structure to reverse a given linked list. Problems involving reversing something (strings, series of characters, numbers, lists etc), can mostly be solved using stacks.
Stack is a last in first out (LIFO) data structure. We push and pop elements from the top of stack. We can use this to our advantage to reverse the given list.
Notice: We will soon publish a detailed article on stack data structure.
The idea is to first push all the nodes of the given linked list into the stack, then pop them one by one and reconnect the nodes thereby reversing the list.
The intuition behind this approach is based on the fact that the list nodes that are pushed into stack (from start to end) when popped out will be in reverse order.
For a given linked list this algorithm does the following steps:
Traverse the given singly linked list starting from the head node.
As we visit each node, we add it to the top of stack.
We need to do this for all the nodes in the list.
Once all the nodes are added to stack, pop them one be one.
Make the first node to be popped from stack as the head of linked list (this is the last node in the original list).
For all the other popped nodes, connect the next pointer of previously popped node to the current popped node.
Lets understand this with an example. Consider you are given the below linked list:
Lets take a stack to store these nodes. Initially the stack is empty as shown below:
Traverse the linked list starting from the head node and add them to stack. So we begin by adding node 1 to stack.
Next we move our current pointer to node 2, add node 2 to stack.
Finally we add node 3 to stack.
Now that all the linked list nodes are added to stack, we need to pop them one by one from stack.
First we pop node 3 from stack. Since node 3 is the first node to be popped, we make it the head node of the linked list.
Next we pop node 2 from stack. Also we need to connect the next of previously popped node, node 3, to the current node, node 2.
Finally we pop node 1 from stack and connect the next of node 2 to node 1. As you can see, we have successfully reversed the given linked list using stack.
Implementation
Language: Go
Stack Implementation
Complexity Analysis
Time Complexity: O(n)
In this approach we need to visit each node in the list twice to reverse it (once to add it to the stack, and again to pop it from stack). So, the time complexity is O(n) + O(n) = 2 * O(n) which in general can be represented as O(n).
Space Complexity: O(n)
Space complexity is also O(n) since we store each node in stack.
Want to master coding? Looking to learn new skills and crack interviews? We recommend you to explore these tailor made courses:
Solution 2: Flipping the next pointer
Solution 1 reverses the list in O(n) time but it also needs O(n) space because we use stack to store nodes. Also we need to visit each node twice.
This problem can be efficiently solved by simply flipping the next pointer of each node (to point to the previous node). For a given linked list, this algorithm does the following steps:
Take 3 pointer variables: current, previous and next each of which point to the current, previous and next nodes respectively.
Initially current points to the head node and previous points to null.
In each iteration, point next to current.next, and connect current.next to previous which flips the next pointer of the current node.
After that move the next and previous pointers ahead by one node.
Repeat this for all the nodes in the list.
Finally make the last node as the new head of the list.
Let us understand this with an example. Consider you are given the below linked list:
Iteration 1
To begin with current points to head node and previous points to null as shown in the figure below:
Now flip the next pointer of the current node by first pointing next to current.next and then pointing current.next to previous.
Node 1 is now completely processed, so move the current and previous pointers ahead by one step.
Iteration 2
Now node 2 is the current node. Process node 2 similar to node 1 to flip its next pointer.
Move the current and previous pointer to the next node.
Iteration 3
Finally process node 3 in the same way by pointing next to current.next, current.next to previous.
Since node 3 is the last node in our list, we stop our algorithm here. Also one final thing we need to do is to make the last node as our new head as shown in figure below:
Implementation
Language: Go
Language: Java
Complexity Analysis
Time Complexity: O(n)
In this algorithm we need to visit each node in the given linked list only once. So time complexity is O(n).
Space Complexity: O(1)
No extra space is used.
Now you know how to reverse a singly linked list. Do not stop here, deepen your knowledge by exploring more articles on linked lists.
That is all for this article, thank you for taking your time to read this. If you have any questions or doubts, please let us know in the comments section below, we will be happy to answer you.
If you found this article useful, do not forget to subscribe to our website, your support motivates us to bring out more such articles in future (scroll down to the bottom of the page to find the subscription form).
You can explore more such amazing articles from code recipe here.
Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time: Join now
