Rotate List

Medium
2004.

Rotate List

Rotate List is a medium coding problem on two pointers, asked in Amazon, Microsoft, Bloomberg and LinkedIn interviews.

Given the head of a singly linked list, rotate the list to the right by k places: k times, the last node moves to the front. Return the head of the rotated list.

Example 1

Input
head = [1,2,3,4,5], k = 2
Output
[4,5,1,2,3]
Explanation
One rotation gives [5,1,2,3,4], a second gives [4,5,1,2,3].

Example 2

Input
head = [0,1,2], k = 4
Output
[2,0,1]
Explanation
Rotating a 3-node list 3 times brings it back, so 4 rotations equal 1.

Example 3

Input
head = [], k = 7
Output
[]

Constraints

  • The number of nodes in the list is in the range [0, 500]
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Rotate List — Solution in Python, Java & C++

Rotate List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on two pointers.

Rotate List is a medium coding problem on two pointers, asked in Amazon, Microsoft, Bloomberg and LinkedIn interviews.

Problem statement

Given the head of a singly linked list, rotate the list to the right by k places: k times, the last node moves to the front. Return the head of the rotated list.

Example 1

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Explanation: One rotation gives [5,1,2,3,4], a second gives [4,5,1,2,3].

Example 2

Input: head = [0,1,2], k = 4
Output: [2,0,1]
Explanation: Rotating a 3-node list 3 times brings it back, so 4 rotations equal 1.

Example 3

Input: head = [], k = 7
Output: []

Constraints

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

Hints for Rotate List

  1. Hint 1

    Rotating a list of length n by n changes nothing, so only k % n matters — k can be two billion.

  2. Hint 2

    After rotating by s = k % n, the last s nodes come first. The new tail is the node at position n - s (1-based).

  3. Hint 3

    Find the length and the old tail in one walk, link the tail to the head to form a ring, walk to the new tail, and cut the ring after it.

How to solve Rotate List

A right rotation by s moves the last s nodes to the front. Closing the list into a ring and cutting it at the right place does that with two pointer changes.

Approach

  1. If the list is empty, return it.
  2. Walk to the last node, counting the length n.
  3. Set s = k % n; if s == 0 return head.
  4. Link the tail to head, then walk n - s steps from the tail (or n - s - 1 from the head) to the new tail.
  5. The node after it is the new head; set the new tail's next to null and return the new head.

Why it works

In the ring every node keeps its successor, so the order is unchanged up to where we cut; cutting after position n - s makes position n - s + 1 the first node, which is exactly the list rotated right by s.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Simulating k single rotations is far too slow for k up to 2·10^9 — reduce k modulo the length first.
  • Guard the empty list before taking k % n (division by zero).
  • When k % n == 0 return the list unchanged rather than cutting the ring in the wrong place.

Reference solution

Python

from typing import Optional

def rotateRight(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    if head is None:
        return head
    n = 1
    tail = head
    while tail.next:
        tail = tail.next
        n += 1
    s = k % n
    if s == 0:
        return head
    tail.next = head
    new_tail = head
    for _ in range(n - s - 1):
        new_tail = new_tail.next
    new_head = new_tail.next
    new_tail.next = None
    return new_head

Java

public static ListNode rotateRight(ListNode head, int k) {
    if (head == null) return head;
    int n = 1;
    ListNode tail = head;
    while (tail.next != null) { tail = tail.next; n++; }
    int s = k % n;
    if (s == 0) return head;
    tail.next = head;
    ListNode newTail = head;
    for (int i = 0; i < n - s - 1; i++) newTail = newTail.next;
    ListNode newHead = newTail.next;
    newTail.next = null;
    return newHead;
}

C++

ListNode* rotateRight(ListNode* head, int k) {
    if (!head) return head;
    int n = 1;
    ListNode* tail = head;
    while (tail->next) { tail = tail->next; n++; }
    int s = k % n;
    if (s == 0) return head;
    tail->next = head;
    ListNode* newTail = head;
    for (int i = 0; i < n - s - 1; i++) newTail = newTail->next;
    ListNode* newHead = newTail->next;
    newTail->next = nullptr;
    return newHead;
}

JavaScript

var rotateRight = function(head, k) {
    if (head === null) return head;
    var n = 1, tail = head;
    while (tail.next !== null) { tail = tail.next; n++; }
    var s = k % n;
    if (s === 0) return head;
    tail.next = head;
    var newTail = head;
    for (var i = 0; i < n - s - 1; i++) newTail = newTail.next;
    var newHead = newTail.next;
    newTail.next = null;
    return newHead;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 165 two pointers problems · the whole catalogue

Learn the technique: Two Pointers Technique