## Reverse a Linked List from position m to n-Interview Problem Difficulty: Medium

#### 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 mth node and pass it to the reverse function (which will reverse the given part). But, before passing the mth node we need to traverse to the nth 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)
{
return restPart
}
ListNode reverseFromMToN(ListNode head, int m, int n)
{
if(m == n)
int count = 1
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)
{
}
}

}``````
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!!