What pattern does Reverse Linked List II use?

The Pattern: In-place Reversal of a Linked List (Partial Sublist) The Heuristic: When reversing a sublist within a singly linked list, use a dummy node to simplify edge cases and iteratively reverse pointers within the target range, reconnecting the reversed segment seamlessly to the unchanged parts.

Reverse Linked List II - LeetCode Solution

Q: How do you solve Reverse Linked List II?

Create a dummy node pointing to head to handle edge cases. Move a pointer 'prev' to the node immediately before the reversal segment. Then, iterate through the sublist from left to right, reversing the next pointers by standard linked list reversal technique. After reversal, reconnect the reversed sublist back to the main list by adjusting the next pointers of 'prev' and the tail of the reversed sublist. Return dummy.next as the new head.

Q: What is the time complexity of Reverse Linked List II?

O(n). The algorithm traverses the list once to reach the node before the reversal segment and then iterates through the sublist once to reverse pointers, resulting in linear time proportional to the list length.

Problem

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

The number of nodes in the list is n
1 ≤ n ≤ 500
−500 ≤ Node.val ≤ 500
1 ≤ left ≤ right ≤ n

Example

Input: head = [1,2,3,4,5], left = 2, right = 4

Output: [1,4,3,2,5]

The brute-force approach would extract the sublist from position 2 to 4, reverse it separately, and then reattach it, which requires extra space and multiple passes. The optimal approach performs the reversal in-place during a single pass. Starting from the dummy node, the algorithm moves a pointer to the node before the reversal segment (position 1). It then iteratively reverses the links between nodes 2 to 4 by redirecting pointers, effectively reversing the sublist in-place. After the reversal, the sublist is reconnected to the rest of the list, preserving the original order outside the reversed segment.

Approach

Straightforward Solution

A naive solution extracts the sublist into an array or separate list, reverses it, and then reattaches it, resulting in O(n) time but O(k) space where k = right - left + 1.

Core Observation

Reversing a sublist in a singly linked list can be done by changing the next pointers of the nodes within the specified range, without creating new nodes or using extra space.

Path to Optimal

The key insight is to perform the reversal in-place by iterating through the sublist once and reversing the next pointers as you go. Using a dummy node simplifies edge cases where the head is part of the reversed segment. By moving a pointer to the node before the reversal start, the algorithm can reverse the sublist by redirecting pointers in a single pass, achieving O(n) time and O(1) space.

Optimal Approach

Create a dummy node pointing to head to handle edge cases. Move a pointer 'prev' to the node immediately before the reversal segment. Then, iterate through the sublist from left to right, reversing the next pointers by standard linked list reversal technique. After reversal, reconnect the reversed sublist back to the main list by adjusting the next pointers of 'prev' and the tail of the reversed sublist. Return dummy.next as the new head.

Time

O(n)

The algorithm traverses the list once to reach the node before the reversal segment and then iterates through the sublist once to reverse pointers, resulting in linear time proportional to the list length.

Space

O(1)

The reversal is done in-place by pointer manipulation without allocating extra data structures, using only a few pointer variables.

Solution

1class Solution:
2    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
3
4        dummy = ListNode(0, head)
5        prev = dummy
6
7        for _ in range(left - 1):
8            prev = prev.next
9
10        curr = prev.next
11        prev_node = None
12
13        for _ in range(right - left + 1):
14            nxt = curr.next
15            curr.next = prev_node
16            prev_node = curr
17            curr = nxt
18
19        tail = prev.next
20        prev.next = prev_node
21        tail.next = curr
22
23        return dummy.next

1import java.util.*;
2
3class Solution {
4    public ListNode reverseBetween(ListNode head, int left, int right) {
5        ListNode dummy = new ListNode(0, head);
6        ListNode prev = dummy;
7
8        for (int i = 0; i < left - 1; i++) {
9            prev = prev.next;
10        }
11
12        ListNode curr = prev.next;
13        ListNode prevNode = null;
14
15        for (int i = 0; i < right - left + 1; i++) {
16            ListNode nxt = curr.next;
17            curr.next = prevNode;
18            prevNode = curr;
19            curr = nxt;
20        }
21
22        ListNode tail = prev.next;
23        prev.next = prevNode;
24        tail.next = curr;
25
26        return dummy.next;
27    }
28}

1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7    ListNode* reverseBetween(ListNode* head, int left, int right) {
8        ListNode dummy(0, head);
9        ListNode* prev = &dummy;
10
11        for (int i = 0; i < left - 1; i++) {
12            prev = prev->next;
13        }
14
15        ListNode* curr = prev->next;
16        ListNode* prevNode = nullptr;
17
18        for (int i = 0; i < right - left + 1; i++) {
19            ListNode* nxt = curr->next;
20            curr->next = prevNode;
21            prevNode = curr;
22            curr = nxt;
23        }
24
25        ListNode* tail = prev->next;
26        prev->next = prevNode;
27        tail->next = curr;
28
29        return dummy.next;
30    }
31};

1var reverseBetween = function(head, left, right) {
  let dummy = new ListNode(0, head);
  let prev = dummy;
4
  for (let i = 0; i < left - 1; i++) {
      prev = prev.next;
  }
8
  let curr = prev.next;
  let prevNode = null;
11
  for (let i = 0; i < right - left + 1; i++) {
      let nxt = curr.next;
      curr.next = prevNode;
      prevNode = curr;
      curr = nxt;
  }
18
  let tail = prev.next;
  prev.next = prevNode;
  tail.next = curr;
22
  return dummy.next;
24};

Step-by-Step Solution

1

Position Pointer Before Reversal Segment

4dummy = ListNode(0, head)
5prev = dummy
7for _ in range(left - 1):
8    prev = prev.next

Objective

To locate the node immediately before the sublist that needs to be reversed.

Key Insight

Using a dummy node pointing to the head allows uniform handling of cases where the reversal starts at the head. Moving 'prev' forward left - 1 times positions it exactly before the reversal segment, setting up the reversal boundaries precisely.

Interview Quick-Check

Core Logic

Moving 'prev' left - 1 times ensures it points to the node before the reversal start, which is critical for reconnecting the reversed sublist later.

State & Boundaries

The loop runs exactly left - 1 times, which is safe because left >= 1 and the dummy node ensures 'prev' is never null.

Common Pitfalls & Bugs

Failing to use a dummy node can cause errors when left == 1, as there is no node before the head.

2

Reverse the Sublist In-Place by Pointer Rewiring

10curr = prev.next
11prev_node = None
13for _ in range(right - left + 1):
14    nxt = curr.next
15    curr.next = prev_node
16    prev_node = curr
17    curr = nxt

Objective

To reverse the nodes between positions left and right by changing their next pointers.

Key Insight

The reversal uses a standard linked list reversal technique: iteratively detach the current node and insert it at the front of the reversed portion. By maintaining 'prev_node' as the head of the reversed sublist and 'curr' as the current node to process, the algorithm reverses the sublist in a single pass without extra space.

Interview Quick-Check

Core Logic

The loop reverses the sublist by redirecting each node's next pointer to the previously reversed nodes, effectively building the reversed sublist incrementally.

State & Boundaries

The loop runs right - left + 1 times, covering exactly the nodes in the reversal range.

Common Pitfalls & Bugs

Incorrect pointer updates or missing the order of assignments can break the list or cause cycles.

3

Reconnect the Reversed Sublist to the Main List

19tail = prev.next
20prev.next = prev_node
21tail.next = curr

Objective

To link the reversed sublist back into the original list, preserving the overall list structure.

Key Insight

After reversal, 'prev.next' should point to the new head of the reversed sublist ('prev_node'), and the original start of the sublist ('tail') should point to the node following the reversed segment ('curr'). This ensures the reversed segment is correctly integrated without losing any nodes.

Interview Quick-Check

Core Logic

Reconnecting the reversed sublist involves updating two pointers: the node before the reversed segment and the tail of the reversed segment.

State & Boundaries

These pointer updates must happen after the reversal loop to avoid breaking the list during reversal.

Common Pitfalls & Bugs

Failing to reconnect the tail's next pointer to 'curr' can cause the list to terminate prematurely or lose nodes.

4

Return the New Head of the Modified List

23	`return dummy.next`

Objective

To return the head of the updated list after the reversal operation.

Key Insight

Since the original head might have changed (especially if left == 1), returning 'dummy.next' ensures the correct head is returned regardless of whether the head was reversed.

Interview Quick-Check

Core Logic

Returning 'dummy.next' accounts for cases where the head of the list is part of the reversed segment.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 15 Critical

curr.next = prev_node

Reverse 'curr.next' to point to the previously reversed node.

This pointer reversal is the core operation that inverts the sublist links, enabling in-place reversal without extra space.

Line 14 Critical

nxt = curr.next

Store the next node after 'curr' before changing pointers.

Preserving the next node before pointer reversal is critical to avoid losing the rest of the list, enabling safe in-place reversal.

Line 20 Critical

prev.next = prev_node

Connect 'prev.next' to the new head of the reversed sublist.

This reconnection is essential to maintain list integrity, ensuring the node before the reversed segment points to the new sublist head.

Line 21 Critical

tail.next = curr

Connect the tail of the reversed sublist to the node after the reversed segment.

This pointer update prevents list truncation by reconnecting the reversed sublist's tail to the remaining nodes.

Line 4 Core

dummy = ListNode(0, head)

Create a dummy node pointing to the head to simplify edge cases.

The dummy node acts as a fixed anchor before the head, enabling uniform pointer manipulation even when the head is reversed, preventing null pointer exceptions.

Line 7 Core

for _ in range(left - 1):

Move 'prev' forward left - 1 times to reach node before reversal start.

This loop precisely positions 'prev' to the node before the sublist to be reversed, which is essential for reconnecting the reversed sublist later.

Line 19 Core

tail = prev.next

Save the original start of the reversed sublist as 'tail'.

'tail' will become the end of the reversed sublist and must connect to the remainder of the list after reversal.

Line 23 Core

return dummy.next

Return the head of the modified list, skipping the dummy node.

Returning 'dummy.next' ensures the correct head is returned even if the original head was reversed.

Line 5 Core

prev = dummy

Initialize 'prev' pointer to the dummy node.

'prev' will be moved to the node immediately before the reversal segment, so starting at dummy ensures correct positioning.

Line 10 Core

curr = prev.next

Set 'curr' to the first node in the reversal segment.

'curr' marks the start of the sublist to reverse and will be used to traverse and reverse the sublist.

Line 13 Core

for _ in range(right - left + 1):

Iterate through the sublist from left to right inclusive.

This loop covers exactly the nodes that need to be reversed, ensuring no extra nodes are affected.

Line 16 Core

prev_node = curr

Move 'prev_node' forward to 'curr', extending the reversed sublist.

'prev_node' always points to the head of the reversed sublist, so advancing it tracks the new front after each reversal step.

Line 17 Core

curr = nxt

Advance 'curr' to the next node to process.

Moving 'curr' forward ensures the loop progresses through the sublist to reverse all nodes.

Line 8 Standard

prev = prev.next

Advance 'prev' to its next node in each iteration.

Incrementally moving 'prev' ensures it points to the correct node before reversal begins.

Line 11 Standard

prev_node = None

Initialize 'prev_node' as None to track the reversed sublist head.

'prev_node' will hold the head of the reversed portion as nodes are processed, starting empty.

Test Your Understanding

Why is a dummy node used at the start of the list for this reversal algorithm?

The dummy node simplifies handling edge cases where the head of the list is within the reversal range, allowing uniform pointer manipulation without special casing the head.

Don't just read it. Drill it.

Reconstruct Reverse Linked List II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Reverse Linked List II drill

or drill a free problem

1	`class Solution:`
2	`def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:`
3
4	`dummy = ListNode(0, head)`
5	`prev = dummy`
6
7	`for _ in range(left - 1):`
8	`prev = prev.next`
9
10	`curr = prev.next`
11	`prev_node = None`
12
13	`for _ in range(right - left + 1):`
14	`nxt = curr.next`
15	`curr.next = prev_node`
16	`prev_node = curr`
17	`curr = nxt`
18
19	`tail = prev.next`
20	`prev.next = prev_node`
21	`tail.next = curr`
22
23	`return dummy.next`

1	`import java.util.*;`
2
3	`class Solution {`
4	`public ListNode reverseBetween(ListNode head, int left, int right) {`
5	`ListNode dummy = new ListNode(0, head);`
6	`ListNode prev = dummy;`
7
8	`for (int i = 0; i < left - 1; i++) {`
9	`prev = prev.next;`
10	`}`
11
12	`ListNode curr = prev.next;`
13	`ListNode prevNode = null;`
14
15	`for (int i = 0; i < right - left + 1; i++) {`
16	`ListNode nxt = curr.next;`
17	`curr.next = prevNode;`
18	`prevNode = curr;`
19	`curr = nxt;`
20	`}`
21
22	`ListNode tail = prev.next;`
23	`prev.next = prevNode;`
24	`tail.next = curr;`
25
26	`return dummy.next;`
27	`}`
28	`}`

1	`#include <iostream>`
2
3	`using namespace std;`
4
5	`class Solution {`
6	`public:`
7	`ListNode* reverseBetween(ListNode* head, int left, int right) {`
8	`ListNode dummy(0, head);`
9	`ListNode* prev = &dummy;`
10
11	`for (int i = 0; i < left - 1; i++) {`
12	`prev = prev->next;`
13	`}`
14
15	`ListNode* curr = prev->next;`
16	`ListNode* prevNode = nullptr;`
17
18	`for (int i = 0; i < right - left + 1; i++) {`
19	`ListNode* nxt = curr->next;`
20	`curr->next = prevNode;`
21	`prevNode = curr;`
22	`curr = nxt;`
23	`}`
24
25	`ListNode* tail = prev->next;`
26	`prev->next = prevNode;`
27	`tail->next = curr;`
28
29	`return dummy.next;`
30	`}`
31	`};`

1	`var reverseBetween = function(head, left, right) {`
2	`let dummy = new ListNode(0, head);`
3	`let prev = dummy;`
4
5	`for (let i = 0; i < left - 1; i++) {`
6	`prev = prev.next;`
7	`}`
8
9	`let curr = prev.next;`
10	`let prevNode = null;`
11
12	`for (let i = 0; i < right - left + 1; i++) {`
13	`let nxt = curr.next;`
14	`curr.next = prevNode;`
15	`prevNode = curr;`
16	`curr = nxt;`
17	`}`
18
19	`let tail = prev.next;`
20	`prev.next = prevNode;`
21	`tail.next = curr;`
22
23	`return dummy.next;`
24	`};`

4	`dummy = ListNode(0, head)`
5	`prev = dummy`
7	`for _ in range(left - 1):`
8	`prev = prev.next`

Problem

Example

Approach

Solution

Step-by-Step Solution

Position Pointer Before Reversal Segment

Reverse the Sublist In-Place by Pointer Rewiring

Reconnect the Reversed Sublist to the Main List

Return the New Head of the Modified List

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.