Rotate List

Leetcode Problem 61: Rotate List

Problem Summary

Given the head of a linked list and an integer k, rotate the list to the right by k positions — the last k elements are moved to the front of the list, preserving their relative order.

Constraints:

• The list has between 0 and 500 nodes.
• Node values are integers in the range [-100, 100].
• k is a non-negative integer up to 2,000,000,000.

Techniques

• Linked List
• Two Pointers

Solution

import { ListNode } from "../list-node"

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (!head || k === 0) {
        return head
    }

    let dummy = new ListNode(-1, head)
    let slow: ListNode | null = dummy
    let fast: ListNode | null = dummy
    let current: ListNode | null = head
    let total = 0

    while (current) {
        current = current.next
        total++
    }

    let rotation = Math.floor(k % total)

    if (rotation === 0) {
        return head
    }

    for (let i = 0; i < rotation; i++) {
        fast = fast!.next
    }

    while (fast?.next) {
        slow = slow!.next
        fast = fast.next
    }

    let newHead = slow!.next
    slow!.next = null
    fast!.next = head
    head = newHead

    return head
};