61. Rotate List

Intuition

Rotating right by k is equivalent to moving the last k nodes to the front. Rather than shifting nodes one at a time, find the new tail (node at position len - k%len), make the list circular, then break the circle at the right point. The modulo handles k >= len gracefully.

Algorithm

1Walk the list to find its length and keep a reference to the tail node.
2Reduce k: k = len - k % len. If k == len after reduction, no rotation is needed.
3Make the list circular: tail.next = head.
4Walk k steps from the original head; this node becomes the new tail.
5Set head = newTail.next, then newTail.next = null to break the circle.
6Return the new head.

Example Walkthrough

Input: head = [1,2,3,4,5], k = 2

1.Length = 5. k = 5 - 2%5 = 3.
2.Make circular: 5.next = 1.
3.Walk 3 steps from 1: 1 → 2 → 3. New tail = node 3.
4.New head = 3.next = node 4. Break: 3.next = null.
5.Result: [4, 5, 1, 2, 3].

Output: [4, 5, 1, 2, 3]

Common Pitfalls

•Reduce k modulo len first — k can exceed the list length.
•If k % len == 0, the list is unchanged; the circular-then-break approach handles this automatically since walking len steps returns to the original tail.

61.cs


// 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;
    }
}

// Approach: Find the list length and make it circular by connecting the tail back to the head.
// The effective rotation count is k % len. The new tail is at position (len - k%len) from the
// start, so walk exactly that many steps, break the circle there, and the next node is the new head.
//
// Time: O(N) — one pass to find length, one pass to find the new tail.
// Space: O(1) — only a few pointer variables.
public class Solution
{
    public ListNode RotateRight(ListNode head, int k)
    {
        if (head == null || head.next == null || k == 0)
            return head;

        ListNode temp = head;
        int len = 1;

        while (temp.next != null)
        {
            temp = temp.next;
            len++;
        }

        temp.next = head;
        k = len - k % len;

        while (k > 0)
        {
            temp = temp.next;
            k--;
        }

        head = temp.next;
        temp.next = null;
        return head;
    }
}

Was this solution helpful?