Сложность: hard
Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.
k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть.
Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.
Пример:
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
👨💻 Алгоритм:
1️⃣Проходим по списку, находя группы из k узлов.
2️⃣Разворачиваем найденную группу, изменяя ссылки между узлами.
3️⃣Повторяем процесс, пока не обработаем весь список.
😎 Решение:
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if k == 1:
return head
def reverse(first, last, pre_first):
nonlocal head
if pre_first:
pre_first.next = last
else:
head = last
prev, curr = first, first.next
first.next = last.next
for _ in range(k-1):
curr.next, prev, curr = prev, curr, curr.next
count = 1
curr = first = head
pre_first = None
while curr:
if count == k:
reverse(first, curr, pre_first)
pre_first = first
curr, first = first.next, first.next
count = 1
else:
curr = curr.next
count += 1
return head
Ставь 👍 и забирай 📚 Базу знаний