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

Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.

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

Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.

Пример:

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

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

1⃣Пройти по списку, чтобы определить его длину.

2⃣Развернуть группы из k узлов, меняя ссылки, а не значения.

3⃣Если оставшиеся узлы менее k, оставить их без изменений.

😎 Решение:

public class Solution {
    public ListNode ReverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prevGroupEnd = dummy;
        
        while (true) {
            ListNode groupStart = prevGroupEnd.next;
            ListNode groupEnd = prevGroupEnd;
            
            for (int i = 0; i < k; i++) {
                groupEnd = groupEnd.next;
                if (groupEnd == null) return dummy.next;
            }
            
            ListNode nextGroupStart = groupEnd.next;
            Reverse(groupStart, groupEnd);
            
            prevGroupEnd.next = groupEnd;
            groupStart.next = nextGroupStart;
            prevGroupEnd = groupStart;
        }
    }

    private void Reverse(ListNode start, ListNode end) {
        ListNode prev = null, curr = start, next = null;
        while (prev != end) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
    }
}

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