algoadvance

Leetcode 92. Reverse Linked List II

Problem Statement

You are 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.

Example:

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

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500.
• -500 <= Node.val <= 500.
• 1 <= left <= right <= n.

Clarifying Questions

1. Q: What should be returned if left is equal to right? A: If left is equal to right, the list remains unchanged since there’s no range to reverse.

2. Q: Are the node values unique? A: Node values are not necessarily unique.

3. Q: Do we have to handle empty lists? A: No, according to the constraints we assume that the number of nodes is at least 1.

Strategy

1. Initialize Pointers:
   • Use pointers to traverse and manipulate the sublist that needs to be reversed.
   • Use a dummy node to facilitate edge cases where reversing includes the head of the linked list.
2. Traverse to the Start Position:
   • Use a pointer to traverse the list until the node just before the left-th node.
3. Reverse the Sublist:
   • Use another pointer to reverse the specified range of the linked list in-place.
4. Reconnect the Reversed Sublist:
   • Reconnect the start and end of the reversed sublist with the non-reversed parts of the list.
5. Return the New Head:
   • Return the new head, which might be different from the original head if the head was part of the reversed sublist.

Code

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (!head) return nullptr;

        // Create a dummy node to simplify operations
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prev = dummy;
        
        // Move `prev` to the node just before the `left`-th node
        for (int i = 1; i < left; ++i) {
            prev = prev->next;
        }

        // `start` will point to the `left`-th node
        ListNode* start = prev->next;
        // `then` will point to the `left+1`-th node
        ListNode* then = start->next;

        // Reverse the sublist from `left` to `right`
        for (int i = 0; i < right - left; ++i) {
            start->next = then->next;
            then->next = prev->next;
            prev->next = then;
            then = start->next;
        }

        return dummy->next;
    }
};

Time Complexity

• Time Complexity: O(n) where n is the number of nodes in the linked list. We traverse the list to reach the left-th node and perform a constant amount of operations for each node in the sublist to be reversed.
• Space Complexity: O(1) as we are reversing the linked list in place and only using a few auxiliary pointers.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?