You are given the head of a singly linked list and an integer k. Left rotate the list k times and return the new head.
A single left rotation moves the first node to the back: 10 → 20 → 30 becomes 20 → 30 → 10. Do this k times in total.
Note that k can be far larger than the length of the list — rotating a list of n nodes exactly n times leaves it unchanged, so only k mod n rotations actually matter.
n rotations returns the list to its original order, so only k % n rotations actually change anything.head. Skipping this check risks stepping past the end or breaking the list.n - (k % n). Reduce, convert, and reuse the same cut-and-splice.n - k steps and break the ring there.Input: head = [10,20,30,40,50], k = 4 Output: [50,10,20,30,40] Rotate 1: 20 30 40 50 10; Rotate 2: 30 40 50 10 20; Rotate 3: 40 50 10 20 30; Rotate 4: 50 10 20 30 40.
Input: head = [10,20,30,40], k = 6 Output: [30,40,10,20] With n = 4, k = 6 behaves like k = 2, so the first two nodes move to the back.
- 1 <= number of nodes <= 10^5 - 0 <= k <= 10^9 - 0 <= node.data <= 10^9
Rotating a linked list looks like a shuffling chore, but underneath it is a clean cut-and-splice. We start with the naive "rotate one step, repeat" and sharpen it into a single relink that runs in one pass.
head → head.next → … until next is null, counting nodes as you go.next pointer to detach one part of the list and attach it elsewhere.k % n to collapse a huge rotation count into the few that actually change the list.In plain words: take the first k nodes as one block and move that whole block to the end, keeping every node's relative order. Because a full turn of n rotations is a no-op, first reduce k to k % n.
head = 10 → 20 → 30 → 40 → 50 , k = 4 seam after node #4 (the 40): block A = 10 → 20 → 30 → 40 (first k nodes) block B = 50 result = B then A = 50 → 10 → 20 → 30 → 40
Asking two sharp questions before coding shows you have already spotted the traps — the huge k and the empty edge cases.
“How large can k be relative to the number of nodes?”
k can reach 10^9 while the list may be tiny — so I must reduce k modulo n instead of rotating one step at a time.
“What should happen when k is 0 or a multiple of n?”
The list is returned unchanged — no pointers should move.
“Can the list have a single node?”
Then any rotation is a no-op; I return head immediately.
Before I start, I have a couple of clarifying questions.
Since k can be up to a billion, I'll reduce it modulo the list length so I never rotate more than n times.
And if k mod n is zero, or the list has one node, I'll just return the original head.
Rotating n times cycles every node back to its start. So k and k % n produce the identical list. Reducing first turns a billion rotations into at most n - 1 of meaningful work.
After reducing, the answer is just the list split at position k: the first k nodes detach and reattach behind the rest. We never need to move nodes one at a time.
new tail = node #k (index k-1, 0-based) new head = new_tail.next old tail.next = old head (splice the front block to the back) new tail.next = null (close the new end)
A single traversal gives both the length n and the old tail. A second short walk of k - 1 steps lands on the new tail. That's O(n) total with only pointer swaps — no extra memory.
| Brute force | Optimal | |
|---|---|---|
| Idea | Move head to tail, repeat k times | Cut once at position k |
| Time | O(n·k) → O(n²) after mod | O(n) |
| Space | O(1) | O(1) |
The full code for both lives in the Approaches selector below.
Key takeaway
A rotation is a relink, not a reshuffle: reduce k with k % n, find the node at index k, and splice the front block onto the back in one pass.
if list empty or single node: return head n, tail = length and last node (one walk) k = k % n; if k == 0: return head new_tail = node at index k-1 new_head = new_tail.next new_tail.next = null tail.next = head return new_head