付費限定文章

鏈結串列中的Twin Sum的最大值_Leetcode #2130_Leetcode 75題精選

Pigsy Ginx on Unsplash

題目敘述

題目會給我們一個鏈結串列的頭部結點Head node，要求我們計算鏈結串列中的Twin sum最大值是多少？

註: Twin Sum的定義就是頭尾結點相對位置相同的，互相配對加總在一起的值。

例如 給定串列= 1 -> 3 -> 2 -> 5 -> 100 -> 8

1, 8 一組，twin sum = 1 + 8 = 9

3, 100 一組，twin sum = 3 + 100 = 103

2, 5 一組，twin sum = 2 + 5 = 7

整體來看，twin sum的最大值 = 103

題目的原文敘述

測試範例

Example 1:

Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6. 

5 + 1 = 6
4 + 2 = 6
Twin sum 最大值 = 6​

Example 2:

Input: head = [4,2,2,3]
Output: 7
Explanation:
The nodes with twins present in this linked list are:
- Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
- Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
Thus, the maximum twin sum of the linked list is max(7, 4) = 7. 

Example 3:

Input: head = [1,100000]
Output: 100001
Explanation:
There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.

約束條件

Constraints:

• The number of nodes in the list is an even integer in the range [2, 10^5].

結點總數目一定是偶數，而且介於2 ~ 十萬之間。

• 1 <= Node.val <= 10^5

節點值都介於 1 ~ 十萬之間。