Разделите связанный список на 3 части так, чтобы максимальная разница между их размерами была минимальной.

Опубликовано: 22 Сентября, 2022

Для заданного односвязного списка задача состоит в том, чтобы разбить заданный связанный список ровно на три части так, чтобы максимальная разница между длинами разбиваемых связанных списков была минимальной.

Примеры:

Input: 1->2->3->4->5
Output:
1->2
3->4
5
Explanation: 
Consider the splitting of the linked list as:

  1. 1->2: The size is 1.
  2. 3->4: The size is 1.
  3. 5: The size is 1.

The maximum difference between the length of any two splitted linked lists is 1, which is minimum.

Input: 7 -> 2 -> 1
Output:
7
2
1

Подход: выполните следующие шаги, чтобы решить данную проблему:

  • Инициализируйте вектор, скажем, ans[] , который хранит разделенный связанный список
  • Если размер данного связанного списка меньше 3 , то создайте size time связанный список только с одним узлом и связанный список размером 3 с нулевыми узлами, добавить его в вектор ответа и вернуть .
  • Инициализируйте переменную, скажем, minSize как размер / 3 , которая будет минимальным размером связанного списка, который будет разделен, и rem как размер % 3 .
  • Перебирайте связанный список, пока размер не станет равным 0 , и выполните следующие шаги:
    • На каждой итерации, если rem равно 0 , снова итерируйте minSize раз в связанный список и добавьте этот связанный список к ответу и уменьшите rem на 1.
    • В противном случае выполните итерацию (minSize + 1) несколько раз в связанный список и добавьте этот связанный список в ответ .
  • После выполнения вышеуказанных шагов распечатайте весь связанный список, хранящийся в векторе ans[] .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ