Coding Interview PatternsRotate List
MediumFast and Slow Pointers

Rotate List

Explanation & Solution

Practice Problem

Description

Given the head of a linked list, rotate the list to the right by k places.

Input:head = [1,2,3,4,5], k = 2
0
1
1
2
2
3
3
4
4
5
Output:[4,5,1,2,3]
0
4
1
5
2
1
3
2
4
3

Explanation: After rotating right by 1: [5,1,2,3,4]. After rotating right by 2: [4,5,1,2,3].

Constraints

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

Approach

Fast and Slow Pointers pattern

1. Handle Edge Cases

  • If the list is empty, has only one node, or k is 0, return the list as-is.

2. Find the Length and Tail

  • Traverse the list to find its total length and a reference to the tail node.

3. Normalize k

  • Compute k = k % length to handle cases where k is larger than the list length.
  • If k becomes 0 after normalization, the list stays unchanged — return it directly.

4. Make the List Circular

  • Connect tail.next = head to form a circular linked list.

5. Find the New Tail

  • The new tail is at position length - k - 1 from the original head.
  • Walk length - k - 1 steps from head to reach it.
  • The node right after the new tail becomes the new head.

6. Break the Circle

  • Set newTail.next = null to break the circular connection.
  • Return the result starting from newHead.

Key Insight

  • Rotating right by k is equivalent to taking the last k nodes and moving them to the front.
  • Making the list circular simplifies the pointer manipulation — we only need to find where to "cut".
Time
O(n)two passes through the list at most.
Space
O(1)only a few pointer variables are used (excluding the output array).

Visualization

Input:
Linked List Traversal
—
1021324354null

Press play to start traversal

Slow (S)Fast (F)Both
8 steps

Solution Code

Previous
Remove Duplicates from Sorted List II
Next
Odd Even Linked List