Scale Engineer

Rotate List

Med
#0061Time: O(n * (k % n))Space: O(1)11 companies
Patterns
Two Pointers
Data structures
Linked List
Companies
AdobeAmazonAppleBloomberg

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the rotation process directly. We rotate the list to the right by one position and repeat this operation k times. A key optimization is to first calculate the effective number of rotations, k % n, where n is the length of the list, to handle large values of k.

Algorithm

  • If head is null, head.next is null, or k is 0, return head.
  • Calculate the length of the list, n.
  • Calculate k = k % n. If k == 0, return head.
  • Repeat k times:
    • Traverse to the end of the list to find the last node (last) and the second-to-last node (secondLast).
    • Set secondLast.next = null.
    • Set last.next = head.
    • Update head = last.
  • Return head.

Walkthrough

The core idea is to perform the rotation one step at a time. To rotate the list to the right by one, we need to move the last element to the front. This involves finding the last and second-to-last nodes, making the last node the new head, and adjusting the pointers accordingly. This entire process is repeated k times.

To avoid unnecessary rotations when k is larger than the list length n, we first compute the effective number of rotations as k' = k % n. If k' is 0, the list remains unchanged. Otherwise, we perform the single-step rotation k' times.

Here is the algorithm:

  1. Handle edge cases: an empty list, a single-node list, or k=0.
  2. Calculate the list's length, n.
  3. Compute k = k % n. If k is 0, return the original list.
  4. Loop k times: a. Find the last node and its predecessor (the second-to-last node). b. Set the next of the second-to-last node to null. c. Set the next of the last node to the current head. d. Update the head to be the last node.
  5. Return the modified head.
/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode rotateRight(ListNode head, int k) {        if (head == null || head.next == null || k == 0) {            return head;        }         // Find the length of the list        int n = 1;        ListNode current = head;        while (current.next != null) {            current = current.next;            n++;        }         // Calculate effective rotations        k = k % n;        if (k == 0) {            return head;        }         // Rotate k times        for (int i = 0; i < k; i++) {            ListNode last = head;            ListNode secondLast = null;            while (last.next != null) {                secondLast = last;                last = last.next;            }                        if (secondLast != null) {                secondLast.next = null;                last.next = head;                head = last;            }        }         return head;    }}

Complexity

Time

O(n * (k % n))

Space

O(1)

Trade-offs

Pros

  • Conceptually simple and easy to understand.

Cons

  • Very inefficient, as it requires traversing the list k times.

  • Leads to Time Limit Exceeded on most platforms for large k or n.

Solutions

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode RotateRight ( ListNode head , int k ) { if ( head == null || head . next == null ) { return head ; } var cur = head ; int n = 0 ; while ( cur != null ) { cur = cur . next ; ++ n ; } k %= n ; if ( k == 0 ) { return head ; } var fast = head ; var slow = head ; while ( k -- > 0 ) { fast = fast . next ; } while ( fast . next != null ) { fast = fast . next ; slow = slow . next ; } var ans = slow . next ; slow . next = null ; fast . next = head ; return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem