Максимальная сумма парных элементов связного списка

Средняя
medium , linked list
09 October 2024

Описание задачи #

Реализуйте функцию, которая будет искать максимальную сумму парных элементов связного списка.

Парный элемент для i'го считается элемент с индексом n - i - 1, где 0 <= i <= n / 2 - 1. То есть, для первого элемента списка парным будет считаться последний элемент списка, для второго - предпоследний и так далее.

Ограничения #

Примеры #

  • Элементы списка: [5,4,2,1]

    Ответ: 6

    Пояснение: В списке есть 2 пары элементов: [5, 1] и [4, 2]. Сумма обоих пар равна 6.

  • Входные данные: [4,2,2,3]

    Ответ: 7

    Пояснение: В списке есть 2 пары элементов: [4, 3] и [2, 2]. Максимальная сумма равна 7.

  • Входные данные: [1,100000]

    Ответ: 100001

Решение через преобразование в массив #

Основная сложность этой задачи заключается в использовании связного списка в качестве структуры данных: мы не знаем длину списка и не можем быстро обращаться к элементам по индексу, из-за чего не получается быстро находить парный элемент для текущего узла.

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

Реализация #

  • package maximum_twin_sum_of_a_linked_list

func pairSumSlice(head *ListNode) int {
	list := []int{head.Val}
	for cur := head.Next; cur != nil; cur = cur.Next {
		list = append(list, cur.Val)
	}

	res := 0
	for i := 0; i < len(list)/2; i++ {
		j := len(list) - i - 1
		res = max(res, list[i]+list[j])
	}

	return res
}

  • import { ListNode } from './ListNode';

export function pairSumSlice(head: ListNode): number {
    let list: number[] = [head.val];

    // Проходим по списку и заполняем массив значениями
    for (let cur = head.next; cur !== null; cur = cur.next) {
        list.push(cur.val);
    }

    let res = 0;

    // Находим максимальную пару значений
    for (let i = 0; i < Math.floor(list.length / 2); i++) {
        let j = list.length - i - 1;
        res = Math.max(res, list[i] + list[j]);
    }

    return res;
}

Оценка сложности #

По времени

Для решения нам нужно дважды проитерироваться по всем элементам: первый раз для создания массива, второй для поиска всех сумм.

Итоговая сложность будет равна O(n).

По памяти

O(n) — так как выделяется память для хранения списка в виде слайса.

Решение через стек #

Решение можно улучшить, сэкономив память: нам необязательно превращать весь список в массив. Достаточно переложить первую половину списка в стек, а затем пройти по второй половине, доставая для каждого следующего элемента его пару из стека.

Однако возникает другая проблема: как я уже упоминал, основное ограничение — это незнание длины списка, а значит, мы не можем сразу определить, где находится его середина. Это ограничение можно обойти с помощью небольшой хитрости, используя два указателя:

oddElementList = oddElementList.Next.Next

Таким образом, когда указатель oddElementList достигнет конца списка, указатель currentListElement будет указывать на начало второй половины нашего списка.

После этого останется только пройтись до конца списка указателем currentListElement, доставая для каждого следующего элемента его пару из стека и находя максимальную сумму.

Реализация #

  • package maximum_twin_sum_of_a_linked_list

func pairSumStack(head *ListNode) int {
	stack := make([]int, 0)
	currentListElement, oddElementList := head, head

	for oddElementList != nil && oddElementList.Next != nil {
		stack = append(stack, currentListElement.Val)
		currentListElement = currentListElement.Next
		oddElementList = oddElementList.Next.Next
	}

	res := 0
	for ; currentListElement != nil; currentListElement = currentListElement.Next {
		res = max(res, currentListElement.Val+stack[len(stack)-1])
		stack = stack[:len(stack)-1]
	}

	return res
}

  • import { ListNode } from './ListNode';

export function pairSumStack(head: ListNode): number {
    let stack: number[] = [];
    let currentListElement: ListNode | null = head;
    let oddElementList: ListNode | null = head;

    // Заполняем стек первой половиной списка
    while (oddElementList !== null && oddElementList.next !== null) {
        stack.push(currentListElement!.val);
        currentListElement = currentListElement!.next;
        oddElementList = oddElementList.next.next;
    }

    let res = 0;

    // Сравниваем элементы с конца первой половины и из второй половины
    while (currentListElement !== null) {
        res = Math.max(res, currentListElement.val + stack.pop()!);
        currentListElement = currentListElement.next;
    }

    return res;
}

Оценка сложности #

По времени

Для решения нам нужно один раз проитерироваться по всем элементам.

Итоговая сложность будет равна O(n).

По памяти

O(n) — так как выделяется память для хранения элементов в стеке.

Решение #

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

Чтобы быстро находить пары, можно создать вспомогательный список, развернутый в обратном порядке. Для изменения порядка списка можно написать простую функцию reverseList (изменение происходит in-place без создания нового списка).

Как и в случае со стеком, можно развернуть не весь список, а только одну его половину. Итоговое решение будет очень похоже на решение со стеком, только вместо стека мы будем использовать первую половину списка, развернутую в обратном порядке.

Данное решение будет более оптимальным по памяти, так как изменение порядка происходит in-place и не требует дополнительного пространства под массив или стек.

Реализация #

  • package maximum_twin_sum_of_a_linked_list

type ListNode struct {
	Val  int
	Next *ListNode
}

func pairSum(head *ListNode) int {
	firstHalfList, oddElementList := head, head

	for oddElementList != nil && oddElementList.Next != nil {
		firstHalfList = firstHalfList.Next
		oddElementList = oddElementList.Next.Next
	}

	revers := reverseList(firstHalfList)

	maxSum := 0
	for revers != nil {
		maxSum = max(maxSum, head.Val+revers.Val)
		head, revers = head.Next, revers.Next
	}
	return maxSum
}

func reverseList(head *ListNode) *ListNode {
	var newHead *ListNode = nil
	for head != nil {
		next := head.Next
		head.Next, newHead = newHead, head
		head = next
	}

	return newHead
}

  • import { ListNode } from './ListNode';

export function pairSum(head: ListNode): number {
    let firstHalfList: ListNode | null = head;
    let oddElementList: ListNode | null = head;

    // Ищем середину списка
    while (oddElementList !== null && oddElementList.next !== null) {
        firstHalfList = firstHalfList!.next;
        oddElementList = oddElementList.next.next;
    }

    // Разворачиваем вторую половину списка
    let revers: ListNode | null = reverseList(firstHalfList);

    let maxSum = 0;
    // Сравниваем элементы
    while (revers !== null) {
        maxSum = Math.max(maxSum, head.val + revers.val);
        head = head.next!;
        revers = revers.next;
    }

    return maxSum;
}

function reverseList(head: ListNode | null): ListNode | null {
    let newHead: ListNode | null = null;

    while (head !== null) {
        let next: ListNode | null = head.next;
        head.next = newHead;
        newHead = head;
        head = next;
    }

    return newHead;
}

Оценка сложности #

По времени

Для решения задачи нам достаточно проитерироваться по исходному списку.

Итоговая сложность будет равна O(n).

По памяти

В решении с разворотом половины списка дополнительная память равна O(1).

Оригинал задачи на Leetcode
< Предыдущая задача