Reverse Linked List II (Reverse a Sub-list)

Problem

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

For example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

Thought Process

The problem follows the In-place Reversal of a LinkedList pattern. We can use a similar approach as in Reverse a Linked List I. Here are the steps we need to follow:

1. Skip the first p-1 nodes, to reach the node at position p.

2. Remember the node at position p-1 to be used later to connect with the reversed sub-list.

3. Next, reverse the nodes from p to q using the same approach discussed in Reverse a Linked List I.

4. Connect the p-1 and q+1 nodes to the reversed sub-list.

Solution

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if (n==m):
            return head
        
        prev, curr = None, head
        
        i = 0
        # after skipping 'p-1' nodes, current will point to 'm'th node
        while curr is not None and i < m-1:
            prev = curr
            curr = curr.next
            i+=1
           
        #node previous of mth node so we can connect it
        previousNode = prev
        mThNode = curr
        
        i=0
       
        
        #reversing the elements between p and q
        while curr is not None and i < n-m+1:
            nextN = curr.next
            curr.next = prev
            prev = curr
            curr = nextN
            i+=1
            
        if previousNode is not None:
            previousNode.next = prev
        else: #this means p == 1 i.e., we are changing the first node (head) of the LinkedList
            head = prev 
            
        mThNode.next = curr
        
        return head