DAY 96 - Reverse Linked List II

Hey Guys! Today we are going to daily leetcode problem. Let's get started with it!.

The problem at hand involves reversing a sublist within a singly linked list between specified positions. To briefly understand this, please be acquainted with how to reverse a linked list or the core concept behind it.

Problem: Reverse Linked List II

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.

Understanding the Approach(Intuition)

Before diving into the code, let's understand the intuition behind the approach used in the provided C++ code.

• We create a dummy node at the beginning of the list to handle the case where the sublist starts from the first node. This simplifies the code.

• We initialize a prev pointer to point to the node just before the left-th node. We iterate until prev reaches the node before left.

• We maintain a curr pointer to keep track of the current node which will be moved to the position right after prev.

• We then reverse the sublist from left to right by iteratively moving nodes between left and right. This is achieved by adjusting the next pointers of the nodes.

• Finally, we return the modified list with the sublist reversed.

Example Walkthrough

Let's perform a step-by-step walkthrough of the code with an example linked list: 1 -> 2 -> 3 -> 4 -> 5, and left = 2 and right = 4.

1. Initially, a dummy node is created, and prev is set to dummy. The list is: dummy -> 1 -> 2 -> 3 -> 4 -> 5.

2. The prev pointer is moved to the node before left, which is 1. The curr pointer is set to 2. The list remains the same.

3. We enter the loop to reverse the sublist.

   • nextNode is set to 3.
   • curr->next points to nextNode->next, making 2 point to 4.
   • nextNode->next is updated to prev->next, making 3 point to 2.
   • prev->next is updated to nextNode, making 1 point to 3.

The list becomes: dummy -> 1 -> 3 -> 2 -> 4 -> 5.

1. The loop continues, and the same steps are repeated to reverse the remaining part of the sublist.

2. Finally, the modified list is returned without the dummy node.

The Code

Here's the code to reverse a sublist in a linked list:

ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (head == nullptr || left == right) {
        return head;
    }

    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* prev = dummy;

    // Move prev to the node before the left-th node
    for (int i = 1; i < left; ++i) {
        prev = prev->next;
    }

    ListNode* curr = prev->next;

    // Reverse the sublist from left to right
    for (int i = left; i < right; ++i) {
        ListNode* nextNode = curr->next;
        curr->next = nextNode->next;
        nextNode->next = prev->next;
        prev->next = nextNode;
    }

    return dummy->next;
}

Complexity Analysis:

Time Complexity: The algorithm makes a single pass through the list, so the time complexity is O(N), where N is the number of nodes in the list.

Space Complexity: The algorithm uses a constant amount of extra space, so the space complexity is O(1).