Rotate List - CPP Solution

1. Introduction

In this blog post, we address a common problem in linked list manipulation: rotating the list to the right by a certain number of places. This operation involves changing the connections between nodes to shift their positions in the list.

Problem

Given the head of a linked list, the task is to rotate the list to the right by k places, where k is a non-negative integer.

2. Solution Steps

1. Calculate the length of the linked list.

2. Connect the last node to the head to form a circle.

3. Traverse the list to find the new tail, which is length - k % length steps from the beginning.

4. Break the circle by setting the next of the new tail to nullptr and return the new head.

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 rotate the list to the right by k places
ListNode* rotateRight(ListNode* head, int k) {
    if (!head || !head->next || k == 0) return head;

    // Compute the length of the list
    ListNode *current = head;
    int length = 1;
    while (current->next) {
        current = current->next;
        length++;
    }

    // Connect the last node to the head to form a circle
    current->next = head;

    // Find the new tail: (length - k % length - 1)th node
    for (int i = 0; i < length - k % length - 1; i++) {
        head = head->next;
    }

    // Break the circle and set the new head
    current = head->next;
    head->next = nullptr;

    return current;
}

// 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 k = 2;
    head = rotateRight(head, k);
    printLinkedList(head); // Expected output for k=2: 4 -> 5 -> 1 -> 2 -> 3 -> nullptr
    return 0;
}

Output:

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

Explanation:

The rotateRight function rotates the list by first forming a circular linked list and then breaking the circle after the new end of the list, which is determined by the value of k. The rotation is achieved by moving the head pointer to the right k times, accounting for the possibility of k being larger than the length of the list. The list is then 'cut' at the new tail, setting its next to nullptr, and returning the new head. This approach efficiently rotates the list without actually moving the nodes but by merely reassigning pointers.