Sponsored
Sponsored
This approach involves reversing the sublist in place by iterating from the left to the right node. We will use a dummy node to ensure that edge cases where the reversal starts at the head of the list are handled smoothly. During the iteration, we carefully manipulate the pointers to reverse the section of the list between the given positions.
Time Complexity: O(n), where n is the number of nodes in the list. We do a single pass over the list between left and right.
Space Complexity: O(1), since no additional data structures are used.
1public class Solution {
2 public ListNode reverseBetween(ListNode head, int left, int right) {
3 if (head == null) return null;
4
5 ListNode dummy = new ListNode(0);
6 dummy.next = head;
7 ListNode prev = dummy;
8
9 for (int i = 0; i < left - 1; i++)
10 prev = prev.next;
11
12 ListNode start = prev.next;
13 ListNode then = start.next;
14
15 for (int i = 0; i < right - left; i++) {
16 start.next = then.next;
17 then.next = prev.next;
18 prev.next = then;
19 then = start.next;
20 }
21
22 return dummy.next;
23 }
24}In this Java solution, we create a dummy node for handling the initial segment and simplifying rotations when left is precisely the first node. The procedure works by identifying nodes before the left position and then applying pointer reversal to the segment from left to right.
In this approach, we leverage recursion to reverse the sublist between the given positions. The primary idea is to handle the reversal within the recursive call stack, ensuring the in-place modification of the linked list while managing the sublist reversal inherently through recursive stack control.
Time Complexity: O(n), where n is the total number of nodes in the list.
Space Complexity: O(n), due to recursive call stack depth based on n.
1class ListNode:
2 def __init__(self, val=0, next=
Here, we define a recursive inner function reverse which handles the reversal of the initial segment of the list up to the right-left position. The recursion unfolds with the base case for n = 1. The main function drive adjusts to skip the initial non-reversal nodes as needed before invoking the recursive calls.