61. Rotate List

Linked List
Two Pointers

TIME

O(n)

SPACE

O(1)

Intuition

Rotating a list of length n by k places is the same as rotating it by k % n places. If the effective rotation is 0, the list does not change.

For a non-zero rotation, the new tail is the node at position n - k % n - 1, and the new head is the next node.

Approach

Handle empty lists and single-node lists immediately.
Traverse the list once to find:
- the length n
- the current tail
Reduce k with k %= n.
If k == 0, return head.
Connect the current tail to the current head, temporarily making a cycle.
Move n - k - 1 steps from the original head to find the new tail.
The node after the new tail is the new head.
Break the cycle by setting new_tail.next = None.

Complexity

Time: O(n), the list is traversed a constant number of times
Space: O(1), only pointer variables are used

Edge Cases

Empty list → return None
Single-node list → unchanged
k = 0 → unchanged
k is larger than the list length → use k % n
k is a multiple of n → unchanged

Code

from typing import Optional


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def rotateRight(self, head: Optional["ListNode"], k: int) -> Optional["ListNode"]:
        """
        61. Rotate List
        Time: O(n)
        Space: O(1)
        """
        if not head or not head.next or k == 0:
            return head

        length = 1
        tail = head

        while tail.next:
            tail = tail.next
            length += 1

        k %= length
        if k == 0:
            return head

        tail.next = head
        steps_to_new_tail = length - k - 1
        new_tail = head

        for _ in range(steps_to_new_tail):
            new_tail = new_tail.next

        new_head = new_tail.next
        new_tail.next = None

        return new_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; }
 * }
 */

/**
 * 61. Rotate List
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }

        int length = 1;
        ListNode tail = head;

        while (tail.next != null) {
            tail = tail.next;
            length++;
        }

        k %= length;
        if (k == 0) {
            return head;
        }

        tail.next = head;
        int stepsToNewTail = length - k - 1;
        ListNode newTail = head;

        for (int i = 0; i < stepsToNewTail; i++) {
            newTail = newTail.next;
        }

        ListNode newHead = newTail.next;
        newTail.next = null;

        return newHead;
    }
}