Reverse a Linked List from position M to N

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 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)
    {
        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!!

AfterAcademy Data Structure And Algorithms Online Course — Admissions Open