Reverse a Linked List from position m to n-Interview Problem
Difficulty: Medium
Asked in: Amazon, Facebook, Microsoft
Understanding the problem
Problem Description: Given a head pointer of a Linked List and two positions say m and n, you have to reverse the given Linked List only from position m to position n. Then, return the head of the m to n reversed Linked List.
For Example:
Input: 15->20->25->30->35->NULL, m = 2 and n = 4
Output: 15->30->25->20->35->NULL
Input: 20->40->60->70->NULL, m = 2 and n = 3
Output: 20->60->40->70->NULL
Possible follow-up questions to ask: →
- Is the value of m and n always different? ( Ans: No, it can be same too)
Node Structure of the Linked List:
class ListNode
{
int data
ListNode next
}
Solution
Solution idea
Since we have to reverse a part of the given linked list obviously we need the concept of reversing the linked list. We need to find the m th node and pass it to the reverse function (which will reverse the given part). But, before passing the m th node we need to traverse to the n th node and cut its link with (n+1) th node if present.
Also we have to save the the (m-1) node and also (n+1) th node address so that we can link the reversed part of the linked list again with the original linked list.
Solution steps
We will use following four variable:
1. revPrev → for storing the previous node, i.e. (m-1)th node.
2. revStart → for storing the starting(mth) node of reversal.
3. revEnd → for storing the ending node(nth) of reversal.
4. revNext → for storing the next node, i.e. (n+1)th node.
Now, we will pass revStart to the reverse function and then will attach the reversed part with revStart and revEnd to get the reversed linked list.
Pseudo-Code
ListNode reverse(ListNode head)
{
if(head == NULL || head.next == NULL)
return head
ListNode restPart = reverse(head.next)
head.next.next = head
head.next = NULL
return restPart
}
ListNode reverseFromMToN(ListNode head, int m, int n)
{
if(m == n)
return head
int count = 1
ListNode curr = head
ListNode revPrev = NULL
while(count < m)
{
revPrev = curr
curr = curr.next
count = count + 1
}
ListNode revStart = curr
while(count < n)
{
curr = curr.next
count = count + 1
}
ListNode revEnd = curr
ListNode revNext = curr.next
curr.next = NULL
ListNode revPart = reverse(revStart)
if(revPrev)
{
revPrev.next.next = revNext
revPrev.next = revPart
}
else
{
if(revNext)
{
head.next = revNext
}
head = revPart
}
return head
}
Complexity Analysis
- Time Complexity: O(L), where L is the length of the linked list.
- Space Complexity: O(1)
Critical ideas to think
- Can you implement the reverse function using iteration?
- Can you think of reversing a linked list using a stack?
- Can we reverse a linked list in less than O(n) time? What if it is a doubly linked list?
Suggested Problems to Solve
- Reverse even elements in a Linked List
- Reverse a Doubly Linked List
- Reverse last K elements of a Linked List
- Reverse a Linked List in groups of given size
Happing Coding! Enjoy Algorithms!!