61. Rotate List - Solution & Explanation

The problem

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

Example 1:

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

Example 2:

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

Constraints:

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

Approach overview

Problem Overview: Given the head of a singly linked list, rotate the list to the right by k positions. Nodes shifted past the end wrap around to the front. The challenge is performing this rotation efficiently without repeatedly traversing the list.

Approach 1: Convert to Circular List (Time: O(n), Space: O(1))

The key insight is that rotating a list is equivalent to breaking it at a specific position and reconnecting the ends. First traverse the linked list to compute its length n and locate the tail. Connect the tail back to the head to form a circular list. Since rotating by k where k > n repeats the same rotations, reduce it using k % n. The new tail becomes the n - (k % n) - 1 node from the start, and the next node becomes the new head. Break the circle at the new tail to restore a proper singly linked list.

This approach performs only two linear passes: one to compute length and another to locate the new tail. No extra data structures are required, making the space complexity constant.

Approach 2: Two-Pointer Technique (Time: O(n), Space: O(1))

This method uses the two pointers pattern to locate the rotation split point without explicitly forming a circular list first. Start by computing the length n and reduce rotations with k % n. Move a fast pointer k steps ahead of a slow pointer. Then advance both pointers together until the fast pointer reaches the last node.

At this point, the slow pointer sits at the node just before the new head. Detach the list after the slow pointer, set that next node as the new head, and connect the original tail to the old head. The rotation happens in a single pass after the length calculation.

The two-pointer approach is often preferred when you want a clear pointer movement strategy. It directly identifies the split point using pointer distance rather than temporarily modifying the structure.

Recommended for interviews: Both solutions run in O(n) time with O(1) space, which is the expected optimal complexity for this problem. Interviewers commonly expect the circular list trick because it simplifies the reasoning and reduces pointer edge cases. Demonstrating the two-pointer version shows strong control over pointer manipulation in linked list problems, which is a frequent interview theme.

Approach 1: Approach 1: Convert to Circular List

This approach involves converting the linked list into a circular list and then breaking it at the correct point to achieve the required rotation.

By making the linked list a circular one, you can easily traverse k nodes from the end to set the new head and make necessary detachments.

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or k == 0:
            return head
        # Compute the length of the list
        length = 1
        current = head
        while current.next:
            current = current.next
            length += 1
        current.next = head  # make circular
        k = k % length
        # Calculate the position to break at
        for _ in range(length - k):
            current = current.next
        new_head = current.next
        current.next = None
        return new_head

# Example usage
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
solution = Solution()
rotated_head = solution.rotateRight(head, 2)
current = rotated_head
while current:
    print(current.val, end=' ')
    current = current.next

Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;
        ListNode curr = head;
        int length = 1;
        while (curr.next != null) {
            curr = curr.next;
            length++;
        }
        curr.next = head; // Make it circular
        k = k % length;
        for (int i = 0; i < length - k; i++) {
            curr = curr.next;
        }
        head = curr.next;
        curr.next = null;
        return head;
    }

    public static void main(String[] args) {
        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);

        Solution sol = new Solution();
        head = sol.rotateRight(head, 2);

        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
}

JavaScript

function ListNode(val) {
    this.val = val;
    this.next = null;
}

var rotateRight = function(head, k) {
    if (!head || k === 0) return head;
    let length = 1;
    let current = head;
    while (current.next) {
        current = current.next;
        length++;
    }
    current.next = head; // make it circular
    k %= length;
    for (let i = 0; i < length - k; i++) {
        current = current.next;
    }
    head = current.next;
    current.next = null;

    return head;
};

// Example usage
let 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);
let newHead = rotateRight(head, 2);
let current = newHead;
while (current != null) {
    console.log(current.val);
    current = current.next;
}

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

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

struct ListNode* rotateRight(struct ListNode* head, int k) {
    if (!head || k == 0) return head;
    struct ListNode *curr = head;
    int length = 1;
    while (curr->next) {
        curr = curr->next;
        length++;
    }
    curr->next = head; // Make it circular
    k = k % length;
    for (int i = 0; i < length - k; i++) {
        curr = curr->next;
    }
    head = curr->next;
    curr->next = NULL;
    return head;
}

// Helper function to print the list
void printList(struct ListNode *node) {
    while (node != NULL) {
        printf("%d ", node->val);
        node = node->next;
    }
}

// Example usage
int main() {
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = 1; head->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->val = 2; head->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->next->val = 3; head->next->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->next->next->val = 4; head->next->next->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next->next->next->next->val = 5; head->next->next->next->next->next = NULL;
    head = rotateRight(head, 2);
    printList(head);
    return 0;
}

The Python solution implements the same algorithm. Traverse the list to make it circular by connecting the last node's next pointer to the head. Use the length of the list to handle cases where k is larger than the list length. Break the circle to form the rotated list.

This code also contains a usage example to demonstrate its working.

Complexity

Time Complexity: O(n) because the list is traversed twice.
Space Complexity: O(1) as it modifies the list in place.

Try this approach in the editor

Approach 2: Approach 2: Two-Pointer Technique

In this approach, we utilize a two-pointer technique. We advance one pointer ahead by k nodes and then move another pointer from the start concurrently until the first pointer reaches the list's end. This way, the second pointer will eventually land on the node that will become the new tail.

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or k == 0:
            return head
        # compute the length of the list
        length = 1
        current = head
        while current.next:
            current = current.next
            length += 1
        current.next = head  # make circular
        k = k % length
        # use two pointers to find the break point
        fast = head
        for _ in range(k):
            fast = fast.next
        slow = head
        while fast.next != head:
            slow = slow.next
            fast = fast.next
        new_head = slow.next
        slow.next = None
        return new_head

# Example usage
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
solution = Solution()
rotated_head = solution.rotateRight(head, 2)
current = rotated_head
while current:
    print(current.val, end=' ')
    current = current.next

C++

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || k == 0) return head;
        ListNode* fast = head, *slow = head;
        int length = 1;
        while (fast->next) {
            fast = fast->next;
            ++length;
        }
        fast->next = head;
        k %= length;
        for (int i = 0; i < length - k; i++) {
            slow = slow->next;
            fast = fast->next;
        }
        head = slow->next;
        fast->next = NULL;
        return head;
    }
};

// Example usage
int main() {
    auto *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);

    Solution sol;
    head = sol.rotateRight(head, 2);
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    return 0;
}

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode RotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;
        ListNode fast = head, slow = head;
        int length = 1;
        while (fast.next != null) {
            fast = fast.next;
            length++;
        }
        fast.next = head; // form circular
        k %= length;
        for (int i = 0; i < length - k; i++) {
            slow = slow.next;
            fast = fast.next;
        }
        head = slow.next;
        fast.next = null;
        return head;
    }

    public static void Main() {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        Solution sol = new Solution();
        ListNode newHead = sol.RotateRight(head, 2);
        ListNode curr = newHead;
        while (curr != null) {
            Console.Write(curr.val + " ");
            curr = curr.next;
        }
    }
}

This Python approach uses the length and circular linking technique alongside the two-pointer method. After calculating the mod value to deal with oversized k, a fast pointer forwards to skip k nodes while the slow pointer eventually lands on the desired new tail.

Complexity

Time Complexity: O(n), involving double traversal operations.
Space Complexity: O(1), due to direct manipulation of the existing list structure.

Try this approach in the editor

Approach 3: Fast and Slow Pointers + Link List Concatenation

First, we check whether the number of nodes in the linked list is less than 2. If so, we directly return head.

Otherwise, we first count the number of nodes n in the linked list, and then take the modulus of k by n to get the effective value of k.

If the effective value of k is 0, it means that the linked list does not need to be rotated, and we can directly return head.

Otherwise, we use fast and slow pointers, let the fast pointer move k steps first, and then let the fast and slow pointers move together until the fast pointer moves to the end of the linked list. At this time, the next node of the slow pointer is the new head node of the linked list.

Finally, we concatenate the linked list.

The time complexity is O(n), where n is the number of nodes in the linked list. The space complexity is O(1).

TypeScript

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (!head || !head.next) {
        return head;
    }
    let cur = head;
    let n = 0;
    while (cur) {
        cur = cur.next;
        ++n;
    }
    k %= n;
    if (k === 0) {
        return head;
    }
    let fast = head;
    let slow = head;
    while (k--) {
        fast = fast.next;
    }
    while (fast.next) {
        fast = fast.next;
        slow = slow.next;
    }
    const ans = slow.next;
    slow.next = null;
    fast.next = head;
    return ans;
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	cur := head
	n := 0
	for cur != nil {
		cur = cur.Next
		n++
	}
	k %= n
	if k == 0 {
		return head
	}
	fast, slow := head, head
	for i := 0; i < k; i++ {
		fast = fast.Next
	}
	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}
	ans := slow.Next
	slow.Next = nil
	fast.Next = head
	return ans
}

Rust

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn rotate_right(mut head: Option<Box<ListNode>>, mut k: i32) -> Option<Box<ListNode>> {
        if head.is_none() || k == 0 {
            return head;
        }
        let n = {
            let mut cur = &head;
            let mut res = 0;
            while cur.is_some() {
                cur = &cur.as_ref().unwrap().next;
                res += 1;
            }
            res
        };
        k = k % n;
        if k == 0 {
            return head;
        }

        let mut cur = &mut head;
        for _ in 0..n - k - 1 {
            cur = &mut cur.as_mut().unwrap().next;
        }
        let mut res = cur.as_mut().unwrap().next.take();
        cur = &mut res;
        while cur.is_some() {
            cur = &mut cur.as_mut().unwrap().next;
        }
        *cur = head.take();
        res
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Convert to Circular List	Time Complexity: O(n) because the list is traversed twice. Space Complexity: O(1) as it modifies the list in place.
Approach 2: Two-Pointer Technique	Time Complexity: O(n), involving double traversal operations. Space Complexity: O(1), due to direct manipulation of the existing list structure.
Fast and Slow Pointers + Link List Concatenation	–

Complexity analysis

Approach	Time	Space	When to Use
Convert to Circular List	O(n)	O(1)	Best general solution. Simple logic and minimal pointer handling.
Two-Pointer Technique	O(n)	O(1)	Useful when applying fast/slow pointer patterns in linked list interview problems.

Frequently asked questions

Is Rotate List easy or hard?

Rotate List is considered a medium difficulty problem. The challenge comes from identifying the correct split point and handling edge cases like large k values or lists with a single node.

How to solve Rotate List in O(n)?

First compute the length of the list and reduce rotations using k % n. Either connect the tail to the head to form a circular list or use a two-pointer technique to locate the split point. Once the new tail is identified, detach the list and reconnect nodes so the next node becomes the new head.

What is the best approach for Rotate List?

The most common solution converts the linked list into a temporary circular list, then breaks it at the correct position. This method runs in O(n) time and O(1) space. It avoids repeated rotations and handles large k values efficiently using k % n.

What data structure is used in Rotate List?

The problem is based on a singly linked list. Solutions typically use pointer manipulation and sometimes the two-pointer technique to find the correct rotation point efficiently.

What is the time complexity of Rotate List?

The optimal solution runs in O(n) time, where n is the number of nodes in the linked list. The list is traversed once to compute its length and once more to locate the new tail. Space complexity remains O(1) since only pointer adjustments are performed.

Rotate List Python or Java solution approach

Python and Java implementations follow the same logic: compute the list length, reduce k using modulo, then either form a circular list or use two pointers to find the new tail. Both implementations achieve O(n) time and O(1) extra space.

Is Rotate List asked at Google, Amazon, or Meta?

Rotate List is a common linked list interview question and appears in preparation sets for companies like Amazon, Google, and Meta. The problem tests pointer manipulation, modular arithmetic, and understanding of linked list structure.

Rotate List solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Convert to Circular List

Approach 2: Approach 2: Two-Pointer Technique

Approach 3: Fast and Slow Pointers + Link List Concatenation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Rotate List solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Convert to Circular List

Approach 2: Approach 2: Two-Pointer Technique

Approach 3: Fast and Slow Pointers + Link List Concatenation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems