algoadvance

Leetcode 92. Reverse Linked List II

Problem Statement

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:

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

Clarifying Questions

  1. Are the positions left and right 1-based indices?
    • Yes, the indices are 1-based.
  2. What should be done if left equals right?
    • If left equals right, the list remains unchanged.
  3. Will the input list always have at least one node?
    • Yes, per the problem statement constraints.

Strategy

  1. Traverse to the Starting Point: Traverse the list until reaching the node just before the left-th node.
  2. Reverse Sublist: Reverse the sublist from node left to node right.
  3. Reconnect the Sublist: Reconnect the reversed sublist with the unchanged parts of the list.

Steps:

  1. Use a dummy node to simplify edge cases.
  2. Move to the node just before left (let’s call this pre).
  3. Reverse the sublist from position left to right.
  4. Reconnect the reversed sublist back to the main list.
  5. Return the modified list.

This task requires careful pointer manipulation to ensure the list is correctly reformed after reversing the sublist.

Code

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || left == right) {
            return head;
        }

        // Dummy node initialization
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;

        // Move `pre` pointer to the node just before `left`
        for (int i = 1; i < left; i++) {
            pre = pre.next;
        }

        // `start` will point to the beginning of the sublist to reverse
        ListNode start = pre.next;
        // `then` will point to the node that will be reversed
        ListNode then = start.next;

        // Perform the sublist reversal from `left` to `right`
        for (int i = 0; i < right - left; i++) {
            start.next = then.next;
            then.next = pre.next;
            pre.next = then;
            then = start.next;
        }

        // Return the modified list
        return dummy.next;
    }
}

Time Complexity

The time complexity of this algorithm is ( O(n) ), where ( n ) is the number of nodes in the linked list. The reason is that each node is visited at most twice: once during the initial traversal to find the left position and once more during the reversal process.

Thus, the overall complexity simplifies to ( O(n) ).

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