2130. Maximum Twin Sum of a Linked List

📘 題目敘述

在一個長度為 n 的 linked list 中（n 是偶數），第 i 個節點（0-indexed）與第 (n - 1 - i) 個節點是 twin。

一對 twin 的 twin sum 定義為：它們兩個節點值的總和。給你一個 linked list 的頭節點 head，請回傳所有 twin sum 中的最大值。

條件限制

• linked list 的節點數量為偶數 n
• 2 <= n <= 10^5
• 1 <= Node.val <= 10^5

🧠 解題思路

我用最直觀的方法：先把 linked list 的值全部丟進陣列 nums，再用左右對稱位置計算 twin sum。

因為 twin 定義就是 (i, n - 1 - i)，所以只需要枚舉前半段索引 i = 0 ... n/2 - 1，每次計算 nums[i] + nums[n - 1 - i]，並用 ans 維護最大值。

所有變數

• head：走訪 linked list 用的指標（會一路往後移動）
• nums：把 linked list 所有節點值存成陣列
• n：nums.size()（linked list 長度）
• ans：目前找到的最大 twin sum
• i：計算 twin sum 時的索引（只跑前半段）

🪜 主要流程步驟

1. 走訪 linked list，把所有節點值存進 nums

• while (head)：
• • nums.push_back(head->val)
  • head = head->next

2. 取得長度並初始化答案

• n = nums.size()
• ans = 0

3. 枚舉前半段索引 i，計算對稱 twin sum 並更新最大值

• 對每個 i = 0 ... n/2 - 1：
• • ans = max(ans, nums[i] + nums[n - i - 1])

4. 回傳最大 twin sum

• return ans

💻 程式碼實作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int pairSum(ListNode* head) {
        vector<int> nums;
        while (head) {
            nums.push_back(head->val);
            head = head->next;
        }
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n / 2; i++) {
            ans = max(ans, nums[i] + nums[n - i - 1]);
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/