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.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
8 if not head:
9 return None
10
11 dummy = ListNode(0)
12 dummy.next = head
13 prev = dummy
14
15 for _ in range(left - 1):
16 prev = prev.next
17
18 start = prev.next
19 then = start.next
20
21 for _ in range(right - left):
22 start.next = then.next
23 then.next = prev.next
24 prev.next = then
25 then = start.next
26
27 return dummy.nextThe code initializes a ListNode class to represent each node. The reverseBetween method begins by creating a dummy node that precedes the head of the list, which allows us to manage edge cases where the head itself needs modification.
We identify the node before the left position, referred to as prev, and initiate a standard pointer reversal technique for the sublist. This involves switching the next pointers within the range of left and right to achieve the desired reversal.
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.