LeetCode 2130. Maximum Twin Sum of Linked List

プログラミング
Page content

どうも、たくチャレ(@takuchalle)です。

LeetCodeの2130. Maximum Twin Sum of a Linked Listを解きました。

設問

与えられたLinked Listで、i番目とn-i-1番目のノードがペアになっており、ペアの値の合計値が最大になる値を返す問題。

ノード数は与えられないので、工夫する必要があります。

解

一度配列にデータをpush_backし、要素数が分かったうえで計算していきました。

計算量はO(N)で、消費メモリはO(N)になります。

class Solution {
   public:
    int pairSum(ListNode* head) {
        vector<int> v;
        for (ListNode* node = head; node != nullptr; node = node->next) {
            v.push_back(node->val);
        }

        int n = v.size();
        int max = 0;
        for (size_t i = 0; i < n / 2; i++) {
            int sum = v[i] + v[n - i - 1];
            if (max < sum) max = sum;
        }

        return max;
    }
};

二つのポインタを使って、前半と後半で走査する方法だと追加の消費メモリなしでいけそうです。時間があればやってみようと思います。