algoadvance

Leetcode 61. Rotate List

Problem Statement

Given the head of a linked list, rotate the list to the right by k places.

Example:

Given the linked list: 1->2->3->4->5->NULL and k = 2,
Return: 4->5->1->2->3->NULL

Clarifying Questions

  1. What should I return if the list is empty or has only one node?
    • If the list is empty (head == NULL) or has only one node (head->next == NULL), return the head as it is.
  2. What if k is greater than the length of the list?
    • We can use k % length to rotate because rotating by the length of the list results in the same list.
  3. What kind of elements does the list contain?
    • The elements are integers.
  4. Do I need to handle any special cases, such as negative values of k?
    • No, k is always given as a non-negative integer.

Strategy

  1. Determine the length of the list.
    • Traverse the list to obtain its length. While traversing, connect the last node to the head, forming a circular list.
  2. Calculate the effective number of rotations.
    • Use k % length to determine the number of rotations needed.
  3. Identify the new tail and the new head of the rotated list.
    • The new tail will be at position (length - k % length - 1) and the new head will be the node immediately after the new tail.
  4. Break the list at the new tail and set the new head.
    • Adjust the pointers to complete the rotation and break the circular connection.

Code

#include <iostream>

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

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next || k == 0) return head;

        // Calculate the length of the list
        ListNode* current = head;
        int length = 1; // start from 1 because we are already at head
        while (current->next) {
            current = current->next;
            length++;
        }
        
        // Connect the last node to the head, forming a circular list
        current->next = head;
        
        // Find the point to break the circle at (new tail)
        k = k % length;
        int stepsToNewHead = length - k;
        
        current = head;
        for (int i = 1; i < stepsToNewHead; ++i) {
            current = current->next;
        }
        
        // `current` is now pointing to the new tail
        ListNode* newHead = current->next;
        current->next = nullptr; // Break the circular list
        
        return newHead;
    }
};

// Helper function to print list (for debugging purposes)
void printList(ListNode* head) {
    while (head) {
        std::cout << head->val << " -> ";
        head = head->next;
    }
    std::cout << "NULL" << std::endl;
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI