LeetCode //C - 2130. Maximum Twin Sum of a Linked List-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode //C - 2130. Maximum Twin Sum of a Linked List。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2130. Maximum Twin Sum of a Linked List

In a linked list of size n, where n is even, the $i^{th}$ node (0-indexed) of the linked list is known as the twin of the $n-1-i)^{th}$ node, if 0 <= i <= (n / 2) - 1.

For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Example 1:

LeetCode //C - 2130. Maximum Twin Sum of a Linked List,LeetCode,leetcode,c语言,算法

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.

Example 2:

LeetCode //C - 2130. Maximum Twin Sum of a Linked List,LeetCode,leetcode,c语言,算法

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:

LeetCode //C - 2130. Maximum Twin Sum of a Linked List,LeetCode,leetcode,c语言,算法

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]$ .
$1 <= Node.val <= 10^5$

From: LeetCode
Link: 2130. Maximum Twin Sum of a Linked List文章来源地址https://www.toymoban.com/news/detail-799319.html

Solution:

Ideas：

Use the two-pointer technique to find the middle of the linked list.
Reverse the second half of the list.
Sum the values of the corresponding nodes from the start and reversed second half to find the maximum sum.
Return the maximum sum found.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

int pairSum(struct ListNode* head) {
    if (head == NULL || head->next == NULL) return 0;
    
    // Step 1: Find the middle of the linked list
    struct ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // Step 2: Reverse the second half of the linked list
    struct ListNode *prev = NULL, *next = NULL;
    while (slow) {
        next = slow->next;
        slow->next = prev;
        prev = slow;
        slow = next;
    }
    
    // Step 3: Pairwise sum the values from the start and end to find the maximum sum
    int maxSum = 0;
    struct ListNode *start = head, *end = prev;
    while (end) {
        maxSum = maxSum > (start->val + end->val) ? maxSum : (start->val + end->val);
        start = start->next;
        end = end->next;
    }
    
    // Step 4: Return the maximum sum
    return maxSum;
}