Reverse Linked List II - CPP Solution

1. Introduction

This blog post explores a more complex operation in linked list manipulation: reversing a subsection of a singly linked list. This problem requires a nuanced understanding of pointers and node traversal in linked lists.

Problem

Given the head of a singly linked list and two integers left and right where left <= right, the task is to reverse the nodes of the list from position left to position right and return the reversed list.

2. Solution Steps

1. Initialize two pointers, prev and curr, to traverse the list.

2. Traverse the list until reaching the left position.

3. Utilize three pointers (prev, curr, and next) to reverse the nodes between left and right.

4. Connect the reversed portion with the rest of the list.

5. Return the head of the modified list.

3. Code Program

#include <iostream>
using namespace std;

// Define the ListNode structure
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to reverse the nodes between left and right
ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (!head || left == right) return head;

    ListNode dummy(0);
    dummy.next = head;
    ListNode *prev = &dummy;

    // Traverse until the left position
    for (int i = 0; i < left - 1; i++) {
        prev = prev->next;
    }

    // Start reversing the nodes
    ListNode *curr = prev->next;
    ListNode *next = nullptr;

    for (int i = 0; i < right - left; i++) {
        next = curr->next;
        curr->next = next->next;
        next->next = prev->next;
        prev->next = next;
    }

    return dummy.next;
}

// Function to print the linked list
void printLinkedList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr\n";
}

int main() {
    // Creating a linked list
    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, right = 4;
    head = reverseBetween(head, left, right);
    printLinkedList(head); // Expected output: 1 -> 4 -> 3 -> 2 -> 5 -> nullptr
    return 0;
}

Output:

1 -> 4 -> 3 -> 2 -> 5 -> nullptr

Explanation:

The reverseBetween function reverses the nodes of the list between positions left and right. It first traverses the list to the left position, then uses the three-pointer technique to reverse the nodes in the specified range. The reversed portion is then connected back to the rest of the list. This approach effectively reverses only a portion of the list, keeping the rest of the list intact.