Dare2Solve
Reversing a portion of a singly linked list between two given positions, left
and right
, involves careful pointer manipulation to ensure that the sublist is reversed in place while maintaining the integrity of the rest of the list. The key challenge is to identify the boundaries of the sublist and adjust the pointers to reverse the sublist without disrupting the overall structure of the list.
Initialization:
prev
pointer to traverse to the node immediately before the left
position.Traversal to the Left Position:
prev
pointer to the node just before the left
-th node. This requires left - 1
steps.Reversing the Sublist:
cur
pointer to the left
-th node.left
to right
, adjust the pointers to reverse the links between the nodes in the sublist.temp
pointer to temporarily hold the node after cur
, then adjust the next
pointers to insert temp
at the start of the reversed section.Finalize:
prev
's next will point to the new start of the reversed sublist.next
of the dummy node, which points to the new head of the list.(O(n)), where (n) is the number of nodes in the linked list. We traverse the list up to two times (one for positioning prev
and one for reversing the sublist).
(O(1)), since we are using a constant amount of extra space (a few pointers).
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (!head || left == right) {
return head;
}
ListNode dummy(0, head);
ListNode* prev = &dummy;
for (int i = 0; i < left - 1; ++i) {
prev = prev->next;
}
ListNode* cur = prev->next;
for (int i = 0; i < right - left; ++i) {
ListNode* temp = cur->next;
cur->next = temp->next;
temp->next = prev->next;
prev->next = temp;
}
return dummy.next;
}
};
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
if not head or left == right:
return head
dummy = ListNode(0)
dummy.next = head
prev = dummy
# Move `prev` to the node before the `left`-th node
for i in range(left - 1):
prev = prev.next
# Start reversing the sublist
cur = prev.next
for i in range(right - left):
temp = cur.next
cur.next = temp.next
temp.next = prev.next
prev.next = temp
return dummy.next
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (head == null || left == right) {
return head;
}
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
for (int i = 0; i < left - 1; i++) {
prev = prev.next;
}
ListNode cur = prev.next;
for (int i = 0; i < right - left; i++) {
ListNode temp = cur.next;
cur.next = temp.next;
temp.next = prev.next;
prev.next = temp;
}
return dummy.next;
}
}
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}
*/
var reverseBetween = function (head, left, right) {
if (!head || left === right) {
return head;
}
const dummy = new ListNode(0, head);
let prev = dummy;
for (let i = 0; i < left - 1; i++) {
prev = prev.next;
}
let cur = prev.next;
for (let i = 0; i < right - left; i++) {
const temp = cur.next;
cur.next = temp.next;
temp.next = prev.next;
prev.next = temp;
}
return dummy.next;
};