61. Rotate List

How to solve Rotate List (LeetCode 61): the approach in brief

The problem

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

Pattern

Rotate List is a Linked List Manipulation Patterns problem, in the Reordering / Partitioning subpattern. The pattern covers in-place reversal, merging sorted lists, reordering, and intersection detection

Learn to reorder and partition linked lists. Master techniques like swap pairs, rotate list, and odd-even separation.

Approach outline

1. Think about the properties of linked lists and how you might manipulate pointers to reorder nodes efficiently.
2. Consider that rotating the list by k places means moving the last k nodes to the front; how can you find the length of the list to handle cases where k is larger than the list length?
3. After determining the effective rotation steps (using modulo operation), try to identify the new tail and new head by traversing the list accordingly.

Complexity

The reference solution runs in O(n) time and O(1) space.

Asked at

Rotate List has been reported in interviews at Amazon, Bloomberg, Microsoft, Apple.