🎨Now live: Try our Free AI Image Generation Feature

Intuition
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.
Approach
- Initialization:
- Create a dummy node to simplify edge cases, such as reversing the list from the head. Point the dummy's next to the head of the list.
- Use a
prev
pointer to traverse to the node immediately before theleft
position. - Traversal to the Left Position:
- Move the
prev
pointer to the node just before theleft
-th node. This requiresleft - 1
steps. - Reversing the Sublist:
- Initialize a
cur
pointer to theleft
-th node. - For each node fromleft
toright
, adjust the pointers to reverse the links between the nodes in the sublist. - Specifically, use atemp
pointer to temporarily hold the node aftercur
, then adjust thenext
pointers to inserttemp
at the start of the reversed section. - Finalize:
- After reversing, the
prev
's next will point to the new start of the reversed sublist. - Return thenext
of the dummy node, which points to the new head of the list.
Complexity
Time Complexity:
(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).
Space Complexity:
(O(1)), since we are using a constant amount of extra space (a few pointers).
Code
C++
/**
* 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;
}
};
Python
# 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
Java
/**
* 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;
}
}
JavaScript
/**
* 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;
};