Difficulty: Easy, Asked-in: Microsoft, Amazon, Adobe, SAP Labs, Qualcomm
A head pointer of a linked list is given, write a program to reverse the linked list. We need to reverse the list by changing the links between nodes.
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Input: 1->2->NULL
Output: 2->1->NULL
One idea for reversing a linked list is: Traverse the linked list using a loop and change the next pointer of each node so that it points to its previous node.
Linked list is a linear data structure where each node only points to its next node. So during this process, we should keep track of previous node using some pointer. Before changing the next pointer of the current node, we also need another pointer to track the next node.
Overall, we can use three-pointers for linked list reversal: One for tracking the current node, one for the previous node, and one for the next node. By the end of the loop, we return the new head reference.
We iterate through linked list until curr becomes NULL and keep changing each node's next pointer to its previous node. During this process, we update curr, prev, and forw pointers:
At each step of iteration, partially revered linked list size will grow by one.
ListNode reverseLinkedList(ListNode head)
{
if(head == NULL)
return NULL
ListNode curr = head
ListNode prev = NULL
ListNode forw = NULL
while (curr != NULL)
{
forw = curr->next
curr->next = prev
prev = curr
curr = forw
}
return prev
}
struct ListNode
{
int value;
ListNode* next;
ListNode(int data)
{
value = data;
next = nullptr;
}
};
ListNode* reverseLinkedList(ListNode* head)
{
if (head == nullptr)
return nullptr;
ListNode* curr = head;
ListNode* prev = nullptr;
ListNode* forw = nullptr;
while (curr != nullptr)
{
forw = curr->next;
curr->next = prev;
prev = curr;
curr = forw;
}
return prev;
}
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def reverseLinkedList(head):
if head is None:
return None
curr = head
prev = None
forw = None
while curr is not None:
forw = curr.next
curr.next = prev
prev = curr
curr = forw
return prev
class ListNode
{
int val;
ListNode next;
ListNode(int x)
{
val = x;
next = null;
}
}
public class Solution
{
public ListNode reverseLinkedList(ListNode head)
{
if (head == null)
return null;
ListNode curr = head;
ListNode prev = null;
ListNode forw = null;
while (curr != null)
{
forw = curr.next;
curr.next = prev;
prev = curr;
curr = forw;
}
return prev;
}
}
We are exploring each node and performing constant number of operations at each iteration. So time complexity = n*O(1) = O(1). We use constant extra space, so space complexity = O(1).
The critical question is: How can we solve this problem using recursion? In other words, how can we solve reversing a linked list problem using the solution of its smaller subproblems? Let's think.
Suppose the length of the linked list is n. The idea is to divide linked list into two parts: The head node and remaining linked list of size n - 1 (smaller sub-problem).
We recursively reverse the remaining linked list of size n - 1 by calling the same function with head->next as input parameter. This function will return head pointer of the reversed list of size n - 1 i.e. restListHead = reverseLinkedList (head->next).
After this partial reversal, head node will still point to the last node of the reversed list of size n - 1. In other words, next node of the head will be the last node of the reversed list of size n - 1. For the complete reversal, head should be the last node. So, we do the following operations to ensure this : head->next->next = head, head->next = NULL.
Base case: if (head == NULL || head->next == NULL), return NULL.
ListNode reverseLinkedList(ListNode head)
{
if (head == NULL || head->next == NULL)
return head
ListNode restListHead = reverseLinkedList(head->next)
head->next->next = head
head->next = NULL
return restListHead
}
struct ListNode
{
int value;
ListNode* next;
ListNode(int data)
{
value = data;
next = nullptr;
}
};
ListNode* reverseLinkedList(ListNode* head)
{
if (head == nullptr || head->next == nullptr)
return head;
ListNode* restListHead = reverseLinkedList(head->next);
head->next->next = head;
head->next = nullptr;
return restListHead;
}
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def reverseLinkedList(head):
if head is None or head.next is None:
return head
restListHead = reverseLinkedList(head.next)
head.next.next = head
head.next = None
return restListHead
class ListNode
{
int val;
ListNode next;
ListNode(int x)
{
val = x;
next = null;
}
}
class Solution
{
public ListNode reverseLinkedList(ListNode head)
{
if (head == null || head.next == null)
return head;
ListNode restListHead = reverseLinkedList(head.next);
head.next.next = head;
head.next = null;
return restListHead;
}
}
We are recursively solving the problem of size n with a smaller sub-problem of size n - 1.
Enjoy learning, Enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.
©2023 Code Algorithms Pvt. Ltd.
All rights reserved.