Rotate List - Practice Coding Problems

Rotate List - Problem

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

When we rotate to the right by k places, the last k nodes from the end become the first k nodes at the beginning, and the remaining nodes shift to the right.

Example: If we have list 1→2→3→4→5 and rotate by 2 places, the result is 4→5→1→2→3. The last 2 nodes (4,5) moved to the front.

Input & Output

Example 1 — Basic Rotation

$ Input: head = [1,2,3,4,5], k = 2

› Output: [4,5,1,2,3]

💡 Note: Rotating right by 2 means the last 2 nodes (4,5) move to the front: 1→2→3→4→5 becomes 4→5→1→2→3

Example 2 — Single Rotation

$ Input: head = [0,1,2], k = 4

› Output: [2,0,1]

💡 Note: k=4 with length=3, so effective rotation is 4%3=1. Move last node to front: 0→1→2 becomes 2→0→1

Example 3 — No Rotation Needed

$ Input: head = [1], k = 1

› Output: [1]

💡 Note: Single node list remains unchanged regardless of k value

Constraints

The number of nodes in the list is in the range [0, 500]
-100 ≤ Node.val ≤ 100
0 ≤ k ≤ 2×10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Original linked list: 1→2→3→4→5, k=2

Process

Last k=2 nodes move to front

Output

Rotated list: 4→5→1→2→3

Key Takeaway

🎯 Key Insight: Making the list circular first allows us to rotate efficiently in O(n) time

Asked in

G Google 42 a Amazon 38 M Microsoft 25 f Facebook 22

Brief HTML summary: The key insight is to make the list circular first, then break it at the calculated position. Best approach uses circular connection technique. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Connect and Break	O(n)	O(1)	Find length, make circular, then break at the correct position
Brute Force - Move One by One	O(k×n)	O(1)	Rotate the list one position at a time, k times

Optimized - Connect and Break — Algorithm Steps

Step 1: Find length and make list circular
Step 2: Calculate effective rotation (k % length)
Step 3: Find new tail position and break circle

Visualization

Tap to expand

Step-by-Step Walkthrough

Make Circular

Connect tail to head forming a circle

Find Break Point

Calculate where to break: length - k positions

Break and Return

Break circle at calculated position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* solution(struct ListNode* head, int k) {
    if (head == NULL || head->next == NULL || k == 0) {
        return head;
    }
    
    // Find length and make circular
    int length = 1;
    struct ListNode* tail = head;
    while (tail->next) {
        tail = tail->next;
        length++;
    }
    
    // Connect tail to head to make circular
    tail->next = head;
    
    // Calculate effective rotation
    k = k % length;
    if (k == 0) {
        tail->next = NULL; // Break circle
        return head;
    }
    
    // Find the new tail (length - k - 1 steps from head)
    int stepsToNewTail = length - k;
    struct ListNode* newTail = head;
    for (int i = 0; i < stepsToNewTail - 1; i++) {
        newTail = newTail->next;
    }
    
    // New head is next to new tail
    struct ListNode* newHead = newTail->next;
    newTail->next = NULL; // Break the circle
    
    return newHead;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    struct ListNode* curr = head;
    for (int i = 1; i < size; i++) {
        curr->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        curr->next->val = arr[i];
        curr->next->next = NULL;
        curr = curr->next;
    }
    return head;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array [1,2,3,4,5]
    int arr[100];
    int size = 0;
    char* token = strtok(line, "[,]\n");
    while (token != NULL) {
        if (token[0] >= '0' || token[0] == '-') {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]\n");
    }
    
    int k;
    scanf("%d", &k);
    
    struct ListNode* head = arrayToList(arr, size);
    struct ListNode* result = solution(head, k);
    
    printf("[");
    int first = 1;
    while (result) {
        if (!first) printf(",");
        printf("%d", result->val);
        result = result->next;
        first = 0;
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single traversal to find length plus one more to find break point

✓ Linear Growth

Space Complexity

O(1)

Only using a few pointer variables

✓ Linear Space

892.0K Views

Medium Frequency

~25 min Avg. Time

8.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Connect and Break — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler