This problem requires moving nodes in a linked list so that the last k nodes become the first k nodes. Correctly updating pointers is essential to avoid cycles or broken links. Using a two-pointer approach simplifies locating the rotation point while ensuring O(n) traversal without extra space.
Problem Statement
Given the head of a singly linked list and an integer k, rotate the list to the right by k places. Each rotation moves the last node to the front, repeated k times effectively.
For example, given head = [1,2,3,4,5] and k = 2, the rotated list becomes [4,5,1,2,3]. Another case: head = [0,1,2], k = 4 results in [2,0,1]. Handle empty lists and k larger than the list length carefully.
Examples
Example 1
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Example details omitted.
Example 2
Input: head = [0,1,2], k = 4
Output: [2,0,1]
Example details omitted.
Constraints
- The number of nodes in the list is in the range [0, 500].
- -100 <= Node.val <= 100
- 0 <= k <= 2 * 109
Solution Approach
Calculate list length and normalize k
Traverse the linked list to find its length n. Since rotating by k and k+n are equivalent, compute k modulo n to reduce unnecessary rotations.
Use two-pointer technique to locate new tail
Maintain two pointers separated by k nodes. Move both simultaneously until the front pointer reaches the end. The trailing pointer will mark the new tail after rotation.
Reconnect nodes to perform rotation
Link the old tail to the old head to form a temporary cycle, then break the link after the new tail. Update the head to the node after the new tail to complete rotation.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) because the list is traversed to find its length and then to relocate pointers. Space complexity is O(1) since no extra structures are needed beyond a few pointers.
What Interviewers Usually Probe
- Expect correct pointer updates without creating cycles or losing nodes.
- Check handling of k values larger than the list length.
- Look for proper empty list and single-node edge case handling.
Common Pitfalls or Variants
Common pitfalls
- Not using modulo for k, leading to extra unnecessary rotations.
- Incorrectly updating the tail node, causing cycles or null references.
- Failing to handle lists with length 0 or 1 properly.
Follow-up variants
- Rotate list to the left by k positions instead of right.
- Rotate a doubly linked list using similar pointer adjustments.
- Rotate only a subsegment of the list rather than the entire list.
How GhostInterview Helps
- Provides step-by-step pointer manipulation guidance tailored to linked-list rotations.
- Highlights edge cases like empty lists, single nodes, and large k values automatically.
- Offers a clear, fast-path strategy to locate the new tail using the two-pointer pattern.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the most efficient way to rotate a linked list by k positions?
Use a two-pointer approach to locate the new tail and adjust pointers, computing k modulo list length to avoid unnecessary rotations.
How do I handle k values larger than the linked list length?
Calculate k modulo n, where n is the length of the list, since rotating by n or multiples of n results in the same list.
Can I rotate an empty or single-node list?
Yes, the list remains unchanged, but ensure your code handles these edge cases without null pointer errors.
Why does the two-pointer technique help in Rotate List?
It allows locating the rotation point efficiently without multiple traversals, preventing broken links or cycles.
What are common mistakes when implementing Rotate List?
Failing to update the tail correctly, not using modulo for k, and mishandling empty or single-node lists are the main pitfalls.
Need direct help with Rotate List instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Rotate List from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Remove duplicates from a sorted linked list, leaving only distinct values, and return the modified list in sorted order.
Open problem page#86 Partition ListPartition a linked list such that all nodes less than x come before nodes greater than or equal to x while preserving relative order.
Open problem page#19 Remove Nth Node From End of ListRemove the nth node from the end of a linked list using a two-pointer approach to solve efficiently.
Open problem page