Reverse a Sublist of a Linked List
Problem
Given the head of a singly linked list and 1-indexed positions left and right, reverse the nodes from position left to position right in place. Use a dummy head so we can address the predecessor of left uniformly. Walk forward to the predecessor, then repeatedly take the node after cur and head-insert it just after the predecessor; this reverses the sublist in right - left moves.
Input
1→2→3→4→5, left=2, right=4Output
1→4→3→2→5Only the middle three nodes flip.
def reverse_between(head, left, right):
dummy = ListNode(0, head)
prev = dummy
for _ in range(left - 1):
prev = prev.next
cur = prev.next
for _ in range(right - left):
moved = cur.next
cur.next = moved.next
moved.next = prev.next
prev.next = moved
return dummy.nextfunction reverseBetween(head, left, right) {
const dummy = { val: 0, next: head };
let prev = dummy;
for (let i = 1; i < left; i++) prev = prev.next;
const cur = prev.next;
for (let i = 0; i < right - left; i++) {
const moved = cur.next;
cur.next = moved.next;
moved.next = prev.next;
prev.next = moved;
}
return dummy.next;
}class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0, head), prev = dummy;
for (int i = 1; i < left; i++) prev = prev.next;
ListNode cur = prev.next;
for (int i = 0; i < right - left; i++) {
ListNode moved = cur.next;
cur.next = moved.next;
moved.next = prev.next;
prev.next = moved;
}
return dummy.next;
}
}ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode dummy(0, head);
ListNode* prev = &dummy;
for (int i = 1; i < left; ++i) prev = prev->next;
ListNode* cur = prev->next;
for (int i = 0; i < right - left; ++i) {
ListNode* moved = cur->next;
cur->next = moved->next;
moved->next = prev->next;
prev->next = moved;
}
return dummy.next;
}