DAY 96 - Reverse Linked List II
Tags: leetcode, cpp, coding, algorithms
Published: 2023-09-07 17:34:04


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](https://leetcode.com/problems/reverse-linked-list-ii/description/)

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`.

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

5. Finally, the modified list is returned without the `dummy` node.

---

## The Code

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

```cpp
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).