Задача №25. Reverse Nodes in k-Group
Сложность: hard

Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.
k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то оставшиеся узлы остаются без изменений.
Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.

Пример:

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

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

1⃣Определить k-й узел, чтобы проверить, можно ли перевернуть группу.

2⃣Перевернуть k узлов, обновляя связи между ними.

3⃣Перейти к следующей k-группе и повторить процесс.

😎 Решение:

class Solution { 
    public function reverseKGroup($head, $k) { 
        if ($head === null || $k === 1) { 
            return $head; 
        } 

        $dummy = new ListNode(0); 
        $dummy->next = $head; 
        $groupPrev = $dummy; 

        while (true) { 
            $kth = $this->getKthNode($groupPrev, $k); 
            if ($kth === null) { 
                break; 
            } 

            $groupNext = $kth->next; 
            $prev = $groupNext; 
            $curr = $groupPrev->next; 

            while ($curr !== $groupNext) { 
                $tmp = $curr->next; 
                $curr->next = $prev; 
                $prev = $curr; 
                $curr = $tmp; 
            } 

            $tmp = $groupPrev->next; 
            $groupPrev->next = $kth; 
            $groupPrev = $tmp; 
        } 

        return $dummy->next; 
    } 

    private function getKthNode($curr, $k) { 
        while ($curr !== null && $k > 0) { 
            $curr = $curr->next; 
            $k--; 
        } 
        return $curr; 
    } 
}

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