Разделите связанный список на 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->2: The size is 1.
- 3->4: The size is 1.
- 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)