Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Rotate List

Rotate List

Master this topic with zero to advance depth.

Rotate List

Rotate the list to the right by k places.

Visual Representation

1 -> 2 -> 3 -> 4 -> 5, k = 2 Output: 4 -> 5 -> 1 -> 2 -> 3
Medium
Approach 1

Level III: Cycle + Break

Intuition

Form a cycle, find the new tail (n-k%n), and break.

⏱ O(N)💾 O(1)
java
public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null || k == 0) return head;
    ListNode tail = head; int n = 1;
    while (tail.next != null) { tail = tail.next; n++; }
    tail.next = head; k %= n;
    for (int i = 0; i < n - k; i++) tail = tail.next;
    head = tail.next; tail.next = null;
    return head;
}
Approach 2

Level II: Two Pointers

Intuition

Use two pointers, first and second. Move first k steps ahead. Then move both until first reaches the end. second will then be at the node before the new head.

⏱ O(N)💾 O(1)

Detailed Dry Run

1->2->3->4->5, k=2.

  1. First moves 2 steps to 3.
  2. Move both until First is at 5. Second is at 3.
  3. New head = 3.next = 4.
  4. 3.next = null, 5.next = head.
java
public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null || k == 0) return head;
    ListNode fast = head, slow = head;
    int n = 0;
    while (fast != null) { fast = fast.next; n++; }
    k %= n; if (k == 0) return head;
    fast = head;
    for (int i = 0; i < k; i++) fast = fast.next;
    while (fast.next != null) { fast = fast.next; slow = slow.next; }
    ListNode newHead = slow.next;
    slow.next = null;
    fast.next = head;
    return newHead;
}
← Previous QuestionSwap Nodes in Pairs
Next Question →Convert Sorted List to BST