61. Rotate List
Rotate List (LeetCode 61) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Linked List Manipulation Patterns pattern, in the Reordering / Partitioning subpattern.
How to solve Rotate List
Rotate List is a Linked List Reordering and Partitioning problem, part of Linked List Manipulation Patterns. Learn to reorder and partition linked lists. Master techniques like swap pairs, rotate list, and odd-even separation.
Work towards the solution in these steps:
- Think about the properties of linked lists and how you might manipulate pointers to reorder nodes efficiently.
- 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?
- After determining the effective rotation steps (using modulo operation), try to identify the new tail and new head by traversing the list accordingly.
The reference solution runs in O(n) time and O(1) space.
The Rotate List solution and editorial walks through the full approach with reference code.
Problem statement
Given the head of a linked list, rotate the list to the right by k places.
Example 1:
Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3]
Example 2:
Input: head = [0,1,2], k = 4 Output: [2,0,1]
Constraints:
- The number of nodes in the list is in the range [0, 500].
- -100 <= Node.val <= 100
- 0 <= k <= 2 109
Topics and companies
Topics: Linked List, Two Pointers.
Reported in interviews at Amazon, Bloomberg, Microsoft, Apple.
How to practise Rotate List on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Rotate List in the code editor, or read the Rotate List editorial for a worked solution with its approach and complexity analysis.
Where Rotate List sits in the DSA pattern sheet
- Linked List Manipulation Patterns pattern guide
- Reordering / Partitioning subpattern
- The full DSA patterns sheet
Problems related to Rotate List
Other problems that use the same Reordering / Partitioning and Linked List Manipulation Patterns techniques:
- Insert Greatest Common Divisors in Linked List — Medium, same subpattern
- Odd Even Linked List — Medium, same subpattern
- Partition List — Medium, same subpattern
- Reorder List — Medium, same subpattern
- Swap Nodes in Pairs — Medium, same subpattern
- Add Two Numbers — Medium, same pattern
Rotate List FAQ
What is the LeetCode number of Rotate List?
Rotate List is LeetCode problem 61, rated Medium.
What pattern is used to solve Rotate List?
Rotate List is a Linked List Reordering and Partitioning problem. It belongs to the Linked List Manipulation Patterns pattern, in the Reordering / Partitioning subpattern.
What is the time complexity of Rotate List?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Rotate List?
Rotate List has been reported in interviews at Amazon, Bloomberg, Microsoft, Apple.