Problem Explanation

Given a singly-linked list, we want to reverse a section of the nodes between positions m and n while preserving the rest of the list. Here, position is defined as the index in the list, with the first node having index 1.

Example

Consider the linked list 1 -> 2 -> 3 -> 4 -> 5 -> NULL with m = 2 and n = 4.

Following the given conditions, our task is to reverse the sublist from position m to n, i.e., 2 -> 3 -> 4 in this case. So the reversed sublist would be 4 -> 3 -> 2, and the entire list would then be rearranged as 1 -> 4 -> 3 -> 2 -> 5 -> NULL.

Solution Approach

The solution involves a recursive approach to reverse the sublist using a head-first insertion.

The key idea is that while recursively reversing a part of the list, we simultaneously reverse another part of the list.

Starting from the head of the list, if m is not 1, move the head to the next node until m equals 1.

When m reaches 1, start reversing n nodes using recursion. The recursion also involves setting the next pointer of near head node to the node next to the last node in reversed list (n+1 node).

Finally, return the updated list.

Python Solution

1
2python
3class Solution:
4    next = None
5    def reverseBetween(self, head: 'ListNode', m: int, n: int) -> 'ListNode':
6        if m == 1:
7            return self.reverseN(head, n)
8        head.next = self.reverseBetween(head.next, m - 1, n - 1)
9        return head
10    
11    def reverseN(self, head: 'ListNode', n: 'int') -> 'ListNode':
12        if n == 1:
13            self.next = head.next
14            return head
15        last  = self.reverseN(head.next, n - 1)
16        head.next.next = head
17        head.next = self.next
18        return last

Java Solution

1
2java
3public class Solution {
4    private ListNode nextNode = null;
5    
6    public ListNode reverseBetween(ListNode head, int m, int n) {
7        if (m == 1) {
8            return reverseN(head, n);
9        }
10        head.next = reverseBetween(head.next, m - 1, n - 1);
11        return head;
12    }
13
14    private ListNode reverseN(ListNode head, int n) {
15        if (n == 1) {
16            nextNode = head.next;
17            return head;
18        }
19        ListNode last = reverseN(head.next, n - 1);
20        head.next.next = head;
21        head.next = nextNode;
22        return last;
23    }
24}

JavaScript Solution

1
2javascript
3var reverseBetween = function(head, m, n) {
4    if (m === 1) {
5        return reverseN(head, n);
6    }
7    head.next = reverseBetween(head.next, m - 1, n - 1);
8    return head;
9}
10
11var nextNode = null;
12var reverseN = function(head, n) {
13    if (n === 1) {
14        nextNode = head.next;
15        return head;
16    }
17    let last = reverseN(head.next, n - 1);
18    head.next.next = head;
19    head.next = nextNode;
20    return last;
21};

C++ Solution

1
2cpp
3class Solution {
4public:
5    ListNode* nextNode = nullptr;
6    
7    ListNode* reverseBetween(ListNode* head, int m, int n) {
8        if (m == 1) {
9            return reverseN(head, n);
10        }
11        head->next = reverseBetween(head->next, m - 1, n - 1);
12        return head;
13    }
14    
15    ListNode* reverseN(ListNode* head, int n) {
16        if (n == 1) {
17            nextNode = head->next;
18            return head;
19        }
20        ListNode* last = reverseN(head->next, n - 1);
21        head->next->next = head;
22        head->next = nextNode;
23        return last;
24    }
25};

C# Solution

1
2csharp
3public class Solution {
4    private ListNode NextNode = null;
5    
6    public ListNode ReverseBetween(ListNode head, int m, int n) {
7        if (m == 1) {
8            return ReverseN(head, n);
9        }
10        head.next = ReverseBetween(head.next, m - 1, n - 1);
11        return head;
12    }
13    
14    private ListNode ReverseN(ListNode head, int n) {
15        if (n == 1) {
16            NextNode = head.next;
17            return head;
18        }
19        ListNode last = ReverseN(head.next, n - 1);
20        head.next.next = head;
21        head.next = NextNode;
22        return last;
23    }
24}

Explanation

This solution is a classic application of recursion in linked list problems. The helper function reverseN is used to reverse the first N nodes in a linked list, and keeps track of the (N+1)-th node using the nextNode variable.

The main function reverseBetween first checks if m equals 1, in which case it calls reverseN directly. If m is not 1, the function moves to the next node by making a recursive call with m and n both decremented by 1.

In our reverseN function, when n becomes 1, we save the next node (N+1)-th node in nextNode and return the current node as the new head of the reversed sublist. For n greater than 1, we perform the head-first insertion by making the next node's "next" point to the current head and then setting the head's "next" to be the saved next node (the (N+1)-th node).

This approach ensures that the rest of the list stays intact as we reverse the sublist from position m to n.

Conclusion

Reversing a sublist in a singly-linked list can be achieved by using a recursive approach with head-first insertion. While reversing the sublist, we keep track of the next node to be connected to the original list and make adjustments as we go along. The solution requires a solid understanding of linked list operations and recursion. Solutions provided in Python, JavaScript, Java, C++, and C# demonstrate how the algorithm can be implemented in a variety of programming languages.