Reverse Linked List II

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

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

#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;
}