2130. Maximum Twin Sum of a Linked List

In a linked list of size n, where n is even, the i t h i^{th}ith node (0-indexed) of the linked list is known as the twin of the ( n − 1 − i ) t h (n-1-i)^{th}(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:

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:

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,1 0 5][2, 10^5] [2,105].
  • 1<=Node.val<=1 0 51 <= Node.val <= 10^5 1<=Node.val<=105

From: LeetCode
Link: 2130. Maximum Twin Sum of a Linked List

Solution:

Ideas：
  1. Use the two-pointer technique to find the middle of the linked list.
  2. Reverse the second half of the list.
  3. Sum the values of the corresponding nodes from the start and reversed second half to find the maximum sum.
  4. 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 liststruct 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 liststruct 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 sumint 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 sumreturn maxSum;}