Задача: 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⃣Используем фиктивный узел (dummy) для удобного управления указателями.

3⃣Переворачиваем группы по k узлов, изменяя связи в списке.

😎Решение:

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
    if head == nil || k == 1 {
        return head
    }
    
    let dummy = ListNode(0)
    dummy.next = head
    var current: ListNode? = dummy
    var next: ListNode?
    var prev: ListNode? = dummy
    
    var count = 0
    while current?.next != nil {
        current = current?.next
        count += 1
    }
    
    while count >= k {
        current = prev?.next
        next = current?.next
        for _ in 1..<k {
            current?.next = next?.next
            next?.next = prev?.next
            prev?.next = next
            next = current?.next
        }
        prev = current
        count -= k
    }
    
    return dummy.next
}

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