Reverse a Linked List from position M to N

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?