Leetcode 92. Reverse Linked List II
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.