## 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!!**