92. Reverse Linked List II

Problem Description

The problem presents us with a singly linked list and two integers, left and right, with the condition that left <= right. The goal is to reverse the nodes in the linked list that fall between the positions left and right (inclusive). The positions are 1-indexed, not 0-indexed, so the first node in the list would be position 1, the second node would be position 2, and so on. Ultimately, the modified linked list should be returned with the specified portion reversed while keeping the rest of the list's original structure intact.

Intuition

To tackle this problem, we need to understand the concept of reversing a linked list and also keeping track of the nodes at the boundaries of the section we want to reverse. The core idea is to iterate through the linked list to locate the node just before the left position (the start of our reversal) and the node at the right position (the end of our reversal).

Upon reaching the left position, we will begin the process of reversing the links between the nodes until we reach the right position. The key points are:

We need a reference to the node just before the left position to reconnect the reversed sublist back to the preceding part of the list.
We need to store the node at the left position as it will become the tail of the reversed sublist and connect to the node following the right position.

This can be achieved with a few pointers and careful reassignments of the next pointers within the sublist. By keeping track of the current node being processed and the previous node within the reversal range, we can reverse the links one by one. Finally, we must ensure we reattach the reversed sublist to the non-reversed parts properly to maintain a functioning linked list.

Learn more about Linked List patterns.

Solution Approach

The solution employs two essential steps: iterating to the specified nodes and reversing the sublist. Here, we use a dummy node to simplify edge case handling, such as when reversing from the first node.

Initialization
- A dummy node is created with its next pointing to the head of the list. This helps manage the edge case where the left is 1, indicating the reversal starting from the head.
- Two pointers, pre and cur, are initially set to the dummy and head nodes, respectively.
Locating the Start Point
- We move the pre pointer left - 1 times forward to reach the node just before where the reversal is supposed to start.
- At this point, pre.next points to the first node to be reversed.
- We also set a pointer q to mark the beginning of the sublist to be reversed (pre.next).
Reversal Process
- A loop runs right - left + 1 times, which corresponds to the length of the sublist to be reversed.
- Within the loop, we perform the reversal. We constantly update the cur.next pointer to point to pre, effectively reversing the link between the current pair of nodes.
- After reversing the link, we need to update the pre and cur pointers. pre moves to where cur used to be, and cur shifts to the next node in the original sequence using the temporary pointer t which holds the unreversed remainder of the list.
Final Connections
- After the loop, the sublist is reversed. However, we still need to connect the reversed sublist back into the main list.
- The pointer p.next is set to pre, which, after the loop termination, points to the right node that is now the head of the reversed sublist.
- The initial left node, which is now at the end of the reversed sublist and pointed to by q, should point to the cur node, which is the node right after the right position or None if right was at the end of the list.
Return the Result
- The function returns dummy.next as the new head of the list, ensuring that whether we reversed from the head or any other part of the list, we have the right starting point.

In summary, the solution takes a careful approach to change pointers and reconnect the nodes to achieve the desired reversal between the left and right indices, while keeping the rest of the list intact.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Assume we have a linked list with elements 1 → 2 → 3 → 4 → 5, and we are asked to reverse the nodes between left = 2 and right = 4. The positions of these elements in the list are: 1 → 2 → 3 → 4 → 5.

Following the solution approach step by step:

Initialization
- Create a dummy node (pre) which points to the head of the list.
- Initialize another pointer (cur) to the head which is the first node (1).
Locating the Start Point
- Since left = 2, we move the pre pointer left - 1 (1 time) forward, and it now points to node 1.
- The pre.next then points to node 2, which is the start of the sublist we want to reverse.
- We set a pointer q to mark the beginning of the sublist to be reversed (pre.next), so q points to node 2.
Reversal Process
- We need to reverse the sublist from position 2 to 4. The loop will run right - left + 1 (4 - 2 + 1 = 3 times).
- In the first loop iteration, cur points to 2 and its next is 3. We temporarily store the node following cur in pointer t (node 3), then set cur.next to pre (node 1), and update pre to cur (node 2). Now cur points to t (node 3).
- We repeat this process for node 3 and 4. Upon completion of the loop, our list looks like 1 → 2 ← 3 ← 4 with pre at 4 and cur pointing to 5.
Final Connections
- We need to make the final connections to integrate the reversed sublist with the rest of the list.
- Connect p.next (the original start node 1) to pre (which is now 4), and q.next (which holds the start of the reversed sublist 2) to cur (node 5 which is the remaining part of the list)
Return the Result
- Return the dummy.next, which points to the new head of the list (node 1).

The modified linked list will now look like 1 → 4 → 3 → 2 → 5, with the nodes between position 2 and 4 reversed.

Solution Implementation

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next
5
6class Solution:
7    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
8        # If the list only contains one node or no reversal is needed, return the head as is.
9        if head.next is None or left == right:
10            return head
11
12        # Initialize a dummy node to simplify edge cases
13        # where the reversal might include the head of the list.
14        dummy = ListNode(0)
15        dummy.next = head
16
17        # This node will eventually point to the node right before
18        # the reversal starts. Initialize it to the dummy node.
19        predecessor = dummy
20
21        # Move the predecessor to the node right before where
22        # the reversal is supposed to start.
23        for _ in range(left - 1):
24            predecessor = predecessor.next
25
26        # Initialize the 'reverse_start' node, which will eventually point to the
27        # first node in the sequence that needs to be reversed.
28        reverse_start = predecessor.next
29        current = reverse_start
30        prev = None
31
32        # This loop reverses the nodes between 'left' and 'right'.
33        for _ in range(right - left + 1):
34            next_temp = current.next
35            current.next = prev
36            prev = current
37            current = next_temp
38
39        # Reconnect the reversed section back to the list.
40        predecessor.next = prev           # Connect with node before reversed part.
41        reverse_start.next = current      # Connect the last reversed node to the remainder of the list.
42
43        # Return the new head of the list, which is the next of dummy node.
44        return dummy.next
45

1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5    int val;
6    ListNode next;
7    ListNode() {}
8    ListNode(int val) { this.val = val; }
9    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
10}
11
12class Solution {
13
14    /**
15     * Reverses a section of a singly-linked list between the given positions.
16     *
17     * @param head The head of the linked list.
18     * @param left The position from where to start the reversal (1-indexed).
19     * @param right The position where to end the reversal (1-indexed).
20     * @return The head of the modified linked list.
21     */
22    public ListNode reverseBetween(ListNode head, int left, int right) {
23        // If there is only one node or no need to reverse, return the original list.
24        if (head.next == null || left == right) {
25            return head;
26        }
27
28        // Dummy node to simplify the handling of the head node.
29        ListNode dummyNode = new ListNode(0, head);
30
31        // Pointer to track the node before the reversal section.
32        ListNode nodeBeforeReverse = dummyNode;
33        for (int i = 0; i < left - 1; ++i) {
34            nodeBeforeReverse = nodeBeforeReverse.next;
35        }
36
37        // 'firstReversed' will become the last node after the reversal.
38        ListNode firstReversed = nodeBeforeReverse.next;
39        // 'current' is used to track the current node being processed.
40        ListNode current = firstReversed;
41        ListNode prev = null;
42
43        // Perform the actual reversal between 'left' and 'right'.
44        for (int i = 0; i < right - left + 1; ++i) {
45            ListNode nextTemp = current.next;
46            current.next = prev;
47            prev = current;
48            current = nextTemp;
49        }
50
51        // Reconnect the reversed section back to the list.
52        nodeBeforeReverse.next = prev;      // Connect with node before reversed part.
53        firstReversed.next = current;       // Connect the last reversed node to the remainder of the list.
54
55        // Return the new head of the list.
56        return dummyNode.next;
57    }
58}
59

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* reverseBetween(ListNode* head, int left, int right) {
14        // If there is only one node or no node to reverse
15        if (!head || left == right) {
16            return head;
17        }
18
19        // Create a dummy node to handle edge cases, such as reversing the head node
20        ListNode* dummyNode = new ListNode(0);
21        dummyNode->next = head;
22
23        // Pointers for the node before the reversing part and the first node to reverse
24        ListNode* preReverse = dummyNode;
25
26        // Iterate to find the node before the left position
27        for (int i = 0; i < left - 1; ++i) {
28            preReverse = preReverse->next;
29        }
30
31        // Start reversing from the left position
32        ListNode* current = preReverse->next;
33        ListNode* nextNode = nullptr;
34        ListNode* prev = nullptr;
35
36        // Apply the reverse from left to right positions
37        for (int i = 0; i < right - left + 1; ++i) {
38            nextNode = current->next; // Save the next node to move on
39            current->next = prev; // Reverse the link
40            prev = current; // Move prev one step forward for the next iteration
41            current = nextNode; // Move to the next node in the list
42        }
43
44        // Adjust the links for the node before left and the node right after the reversed part
45        preReverse->next->next = current; // Connect the reversed part with the rest of the list
46        preReverse->next = prev;          // Connect the start of the reversed list to the previous part
47
48        // Return the new head of the list
49        ListNode* newHead = dummyNode->next;
50        delete dummyNode; // Clean up the memory used by dummyNode
51        return newHead;
52    }
53};
54

1// Definition for singly-linked list.
2class ListNode {
3    val: number;
4    next: ListNode | null;
5    constructor(val: number = 0, next: ListNode | null = null) {
6        this.val = val;
7        this.next = next;
8    }
9}
10
11/**
12 * Reverses a portion of the singly-linked list between positions 'left' and 'right'.
13 *
14 * @param {ListNode | null} head The head of the linked list.
15 * @param {number} left The position to start reversing from (1-indexed).
16 * @param {number} right The position to stop reversing at (1-indexed).
17 * @return {ListNode | null} The head of the modified list.
18 */
19function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
20    // Base case: If the sublist to reverse is of size 0, return the original list.
21    const sublistLength = right - left;
22    if (sublistLength === 0) {
23        return head;
24    }
25
26    // Create a dummy node to handle edge cases seamlessly.
27    const dummyNode = new ListNode(0, head);
28    let previousNode: ListNode | null = null;
29    let currentNode: ListNode | null = dummyNode;
30
31    // Move the currentNode to the position right before where reversal begins.
32    for (let i = 0; i < left; i++) {
33        previousNode = currentNode;
34        currentNode = currentNode.next;
35    }
36
37    // The previousNode now points to the node right before the start of the sublist.
38    const sublistHeadPrev = previousNode;
39    previousNode = null;
40
41    // Reverse the sublist from the 'left' to 'right' position.
42    for (let i = 0; i <= sublistLength; i++) {
43        const nextNode = currentNode.next;
44        currentNode.next = previousNode;
45        previousNode = currentNode;
46        currentNode = nextNode;
47    }
48
49    // Connect the reversed sublist back to the unchanged part of the original list.
50    sublistHeadPrev.next.next = currentNode;
51    sublistHeadPrev.next = previousNode;
52
53    // Return the dummy node's next, which is the new head of the linked list.
54    return dummyNode.next;
55}
56

Time and Space Complexity

The time complexity of the given code can be determined by analyzing the number of individual operations that are performed as the input size (the size of the linked list) grows. The reversal operation within the section of the linked list bounded by left and right is the most significant part of the function.

The code iterates from the dummy node to the node just before where the reversal starts (left - 1 iterations), which is O(left).
Then it reverses the nodes between the left and right position, taking right - left + 1 iterations, which is O(right - left).

Assuming n is the total number of nodes in the linked list, the time complexity is the sum of the two:

O(left) + O(right - left), which is equivalent to O(right). Since right is at most n, the upper bound for the time complexity is O(n).

For space complexity, the code only uses a fixed number of extra variables (dummy, pre, p, q, cur, and t), irrespective of the input size. These variables hold references to nodes in the list but do not themselves result in additional space that scales with the input size. Therefore, the space complexity is O(1), meaning it is constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know