Problem statement

You are given the head of a singly linked list and an integer k. Left-rotate the list k times: one left rotation moves the first node to the end of the list.

Return the head of the rotated list. Note that k may be larger than the length of the list.

Example 1

Input: head = [10,20,30,40,50], k = 4
Output: [50,10,20,30,40]
Explanation: Four left rotations move 10, 20, 30 and 40 to the back, one after another.

Example 2

Input: head = [2,4,7,8,9], k = 3
Output: [8,9,2,4,7]
Explanation: The first three nodes move behind 9 in their order.

Example 3

Input: head = [6,1,5], k = 7
Output: [1,5,6]
Explanation: Every 3 rotations restore a 3-node list, so 7 rotations act like 1.

Constraints

• The number of nodes in the list is in the range [1, 10^5]
• 0 <= k <= 10^9
• 0 <= Node.val <= 10^9

Hints for Rotate a Linked List

1. Hint 1

   Rotating a list of length n exactly n times gives back the same list — only k mod n matters.

2. Hint 2

   After s = k mod n left rotations, the old node at index s is the new head, and the old last node is followed by the old head.

3. Hint 3

   Find the length and the tail in one pass, close the list into a ring (tail.next = head), then walk s steps from the tail and cut the ring there.

How to solve Rotate a Linked List

A left rotation by s = k mod n splits the list after its first s nodes and swaps the two parts. With the tail in hand that is a constant number of relinks.

Approach

1. Walk the list once to find its length n and its last node tail.
2. Let s = k mod n; if s == 0, return head unchanged.
3. Find newTail, the node at index s - 1; the new head is newTail.next.
4. Link tail.next = head, cut newTail.next = null, and return the new head.

Why it works

After s left rotations the order is a[s], …, a[n-1], a[0], …, a[s-1]. The relinks produce exactly that: the run from a[s] to the old tail, then the old head, ending at a[s-1], whose link is cleared.

Complexity

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

Pitfalls

• Simulating k single rotations is far too slow for k up to 10^9 — reduce by n first.
• When k is a multiple of n nothing moves; without the early return the cut would land on the tail and break the list.
• This is a left rotation (LeetCode's Rotate List rotates right).

Reference solution

Python

from typing import Optional

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

Java

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

C++

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

JavaScript

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

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

More two pointers problems

• Merge Two Sorted Linked Lists in Reverse Order Medium
• Segregate Even and Odd Nodes in a Linked List Medium
• Maximum Twin Sum of a Linked List Medium
• Delete the Middle Node of a Linked List Medium
• Swapping Nodes in a Linked List Medium
• Merge In Between Linked Lists Medium