Skip to main content
Talentd

Rotate List - Solution & Explanation

MediumLinked ListTwo Pointers21 min readAsked at: Amazon, Microsoft, Meta +6
Practice this problem

Problem Statement

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 * 109

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.

In this solution, we first determine the length of the list and then make it circular. We perform a modulus operation on k to handle cases where k is greater than the length, effectively making unnecessary additional full rotations. Finally, we iterate over the circular list to the correct point to form a valid, rotated list, detaching the circle.

Code

CJavaPythonJavaScript

C

Java

Python

JavaScript

Complexity

Time Complexity: O(n) because we pass through the list twice, once to find the length and once to find the new head.
Space Complexity: O(1) since we only use a constant amount of extra space.

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.

This C++ solution starts by counting the length and linking the last node to the head to form a loop. It then uses two pointers: a fast pointer that traverses k nodes firstly and a slow pointer that starts from the head. Then moving both forward will find the new head when the fast pointer completes the loop.

Code

C++PythonC#

C++

Python

C#

Complexity

Time Complexity: O(n) because it requires traversal for counting.
Space Complexity: O(1) as no extra space is used.

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).

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Convert to Circular List

Time Complexity: O(n) because we pass through the list twice, once to find the length and once to find the new head.
Space Complexity: O(1) since we only use a constant amount of extra space.

Approach 2: Two-Pointer Technique

Time Complexity: O(n) because it requires traversal for counting.
Space Complexity: O(1) as no extra space is used.

Fast and Slow Pointers + Link List Concatenation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Convert to Circular ListO(n)O(1)Best general solution. Simple logic and minimal pointer handling.
Two-Pointer TechniqueO(n)O(1)Useful when applying fast/slow pointer patterns in linked list interview problems.

Video Solution

Rotate List - Linked List - Leetcode 61 - Python • NeetCode • 61,031 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Rotate List with our built-in code editor and test cases.

Practice on FleetCode
Previous

Rotate Array

Next

Split Linked List in Parts