Rotate List
Medium · Linked Lists · Linked List · Two Pointers
Problem
Given the head of a linked list and a non-negative integer k, rotate the list to the right by k places: one rotation moves the last node to the front. Return the head of the rotated list.
k can be far larger than the number of nodes, so do not perform the rotations one by one.
Examples
Input: head = [10,20,30,40], k = 1 Output: [40,10,20,30]
One rotation moves the last node, 40, to the front.
Input: head = [1,2,3], k = 5 Output: [2,3,1]
Every 3 rotations bring a 3-node list back to where it started, so 5 rotations equal 2.
Constraints
- The list has between 0 and 500 nodes
- -100 <= Node.val <= 100
- 0 <= k <= 2 · 10^9
Approaches
- One rotation at a time, k mod n times — time O(n · (k mod n)), space O(1)
Follow-up
What if the list were circular already and you were handed a pointer to some node? Then rotation is free: the "head" is just which node you call first, and rotating right by k means stepping n - (k mod n) nodes forward.
Related problems
Start free on Cariara · Coding problems · System design studio
