Reverse Linked List II

Given the head of a singly linked list and two integers left and right, reverse the nodes of the list from position left to position right, and return the new head of the reversed sublist. Positions are 1-indexed, meaning the head node is at position 1.

Table of Contents

Example:

Input:

Linked List: 1 -> 2 -> 3 -> 4 -> 5
left = 2, right = 4

Output:

Reversed Linked List: 1 -> 4 -> 3 -> 2 -> 5

Explanation: In the input, the linked list is 1 -> 2 -> 3 -> 4 -> 5, and left = 2, right = 4. After reversing the nodes from position 2 to position 4, the new linked list becomes 1 -> 4 -> 3 -> 2 -> 5.

Solution in C++:

#include <iostream>

// Definition for singly-linked list
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to reverse a linked list from position left to position right
ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (head == nullptr || left == right) {
        return head; // Nothing to reverse or invalid input
    }

    // Create a dummy node to handle the case where left = 1
    ListNode* dummy = new ListNode(0);
    dummy->next = head;

    // Find the node at position (left - 1)
    ListNode* prev = dummy;
    for (int i = 1; i < left; ++i) {
        prev = prev->next;
    }

    // Find the node at position right
    ListNode* curr = prev->next;
    ListNode* end = curr;
    for (int i = left; i <= right; ++i) {
        end = end->next;
    }

    // Reverse the sublist from position left to position right
    while (curr != end) {
        ListNode* nextNode = curr->next;
        curr->next = end->next;
        end->next = curr;
        curr = nextNode;
    }

    // Connect the reversed sublist with the rest of the list
    prev->next = end;

    return dummy->next; // New head of the reversed sublist
}

int main() {
    // Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    int left = 2;
    int right = 4;

    std::cout << "Original Linked List: ";
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->val << " -> ";
        current = current->next;
    }
    std::cout << "nullptr" << std::endl;

    ListNode* reversedHead = reverseBetween(head, left, right);

    std::cout << "Reversed Linked List: ";
    current = reversedHead;
    while (current != nullptr) {
        std::cout << current->val << " -> ";
        current = current->next;
    }
    std::cout << "nullptr" << std::endl;

    return 0;
}

Explanation:

The reverseBetween function takes the head of the linked list and two integers left and right as input and returns the new head of the reversed sublist.
We create a dummy node to handle the case where left = 1. The dummy node is used to connect the reversed sublist with the rest of the list.
We find the node at position (left - 1) using a loop. This node is denoted by prev.
We find the node at position right using another loop. This node is denoted by end.
We reverse the sublist from position left to position right by swapping the next pointers of the nodes accordingly.
After the reversal, curr will be pointing to the node right after the reversed sublist, and end will be pointing to the node that comes after the reversed sublist.
We then connect the reversed sublist with the rest of the list by updating the next pointers of prev and end.

Time Complexity:

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. We traverse the linked list once to find the nodes at positions (left - 1) and right, and then we reverse the sublist in linear time.

Space Complexity:

The space complexity of this solution is O(1) as we use a constant amount of additional space for variables. The reversal is done in-place without using any additional data structures.

Reverse Linked List II

Example:

Solution in C++:

Explanation:

Time Complexity:

Space Complexity:

Related Post

Merge K Sorted Lists

Middle of the Linked List

Linked List Cycle II