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 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:

Example 2:

Example 3:

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 < = N o d e . v a l < = 1 0 5 1 <= 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 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;
}