Reverse Linked List II
Reverse the sublist between positions left and right in place using the dummy-head + head-insertion trick.
3 min read
linked-list
Problem#
Reverse the nodes of the list from position left to right (1-indexed, inclusive). Return the modified list.
Examples#
[1,2,3,4,5], left = 2, right = 4→[1,4,3,2,5][5], left = 1, right = 1→[5]
Constraints#
1 <= n <= 500.
Approach#
Dummy head. Walk to the node before left (call it pre). Use the head-insertion trick: take the node right after pre->next (call it mover) and move it to the front of the segment. Repeat right - left times.
Solution#
class Solution {public: ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode dummy(0, head); ListNode* pre = &dummy; for (int i = 1; i < left; ++i) pre = pre->next; ListNode* curr = pre->next; for (int i = 0; i < right - left; ++i) { ListNode* mover = curr->next; curr->next = mover->next; mover->next = pre->next; pre->next = mover; } return dummy.next; }};func reverseBetween(head *ListNode, left int, right int) *ListNode { dummy := &ListNode{Next: head} pre := dummy for i := 1; i < left; i++ { pre = pre.Next } curr := pre.Next for i := 0; i < right-left; i++ { mover := curr.Next curr.Next = mover.Next mover.Next = pre.Next pre.Next = mover } return dummy.Next}from typing import Optional
class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: dummy = ListNode(0, head) pre = dummy for _ in range(left - 1): pre = pre.next curr = pre.next for _ in range(right - left): mover = curr.next curr.next = mover.next mover.next = pre.next pre.next = mover return dummy.nextfunction reverseBetween(head, left, right) { const dummy = new ListNode(0, head); let pre = dummy; for (let i = 1; i < left; i++) pre = pre.next; const curr = pre.next; for (let i = 0; i < right - left; i++) { const mover = curr.next; curr.next = mover.next; mover.next = pre.next; pre.next = mover; } return dummy.next;}class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy = new ListNode(0, head); ListNode pre = dummy; for (int i = 1; i < left; i++) pre = pre.next; ListNode curr = pre.next; for (int i = 0; i < right - left; i++) { ListNode mover = curr.next; curr.next = mover.next; mover.next = pre.next; pre.next = mover; } return dummy.next; }}function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null { const dummy = new ListNode(0, head); let pre: ListNode = dummy; for (let i = 1; i < left; i++) pre = pre.next!; const curr: ListNode = pre.next!; for (let i = 0; i < right - left; i++) { const mover: ListNode = curr.next!; curr.next = mover.next; mover.next = pre.next; pre.next = mover; } return dummy.next;}Editorial#
The “head-insertion” trick: instead of doing a full segment reverse with three pointers, repeatedly pluck the node after curr and reinsert it right after pre. curr (the segment’s original head) drifts toward the tail naturally as the segment grows. Cleaner than slicing and re-splicing.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#