92. Reverse Linked List II

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

1. 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 the left position.
2. Traversal to the Left Position: - Move the prev pointer to the node just before the left-th node. This requires left - 1 steps.
3. Reversing the Sublist: - Initialize a cur pointer to the left-th node. - For each node from left to right, adjust the pointers to reverse the links between the nodes in the sublist. - Specifically, use a temp pointer to temporarily hold the node after cur, then adjust the next pointers to insert temp at the start of the reversed section.
4. Finalize: - After reversing, the prev's next will point to the new start of the reversed sublist. - Return the next 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;
};