Задача: 61. Rotate List
Сложность: medium

Дан указатель на начало связного списка, поверните список вправо на k позиций.

Пример:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

👨‍💻 Алгоритм:

1⃣Найдите старый хвост и соедините его с головой (old_tail.next = head), чтобы замкнуть кольцо. Одновременно вычислите длину списка n.

2⃣Найдите новый хвост, который находится на позиции (n - k % n - 1) от головы, и новую голову, которая находится на позиции (n - k % n).

3⃣Разорвите кольцо (new_tail.next = None) и верните new_head.

😎 Решение:

function rotateRight($head, $k) {
    if ($head === null) return null;
    if ($head->next === null) return $head;

    $oldTail = $head;
    $n = 1;
    while ($oldTail->next !== null) {
        $oldTail = $oldTail->next;
        $n++;
    }
    $oldTail->next = $head;

    $newTail = $head;
    for ($i = 0; $i < $n - $k % $n - 1; $i++) {
        $newTail = $newTail->next;
    }
    $newHead = $newTail->next;

    $newTail->next = null;
    return $newHead;
}

Ставь 👍 и забирай 📚 Базу знаний