Найдите максимальную попарную сумму в связанном списке, которые равноудалены от начала и конца

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

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

Note: Two nodes (i and j) are equidistant from both ends if the distance of ith node from front is same as distance of jth node from back.

Примеры:

Input: lis = {5, 4, 2, 1}
Output: 6
Explanation: The nodes with pairs present in this linked list are:
Node 0 and node 3 are equidistant having a sum of 5 + 1 = 6.
Node 1 and node 2 are equidistant having a sum of 4 + 2 = 6.
Thus, the maximum sum of equidistant nodes of the linked list is max(6, 6) = 6. 

Input: lis = {4, 2, 2, 3}
Output: 7
Explanation: The nodes with pairs present in this linked list are:
Node 0 and node 3 are equidistant having a sum of 4 + 3 = 7.
Node 1 and node 2 are equidistant having a sum of 2 + 2 = 4.
Thus, the maximum sum of equidistant nodes of the linked list is max(7, 4) = 7. 

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

  • Получите середину и разделите связанный список на две части.
  • Переверните вторую часть , чтобы пройти ее в прямом направлении.
  • Пройдите в обе части и наберите максимальную сумму.
  • Снова восстановите связанный список, снова соединив части, для хорошей практики.

Ниже приведена реализация описанного выше подхода.

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

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