LeetCode //C – 2130. Maximum Twin Sum of a Linked List

本文介绍: 【代码】LeetCode //C – 2130. Maximum Twin Sum of a Linked List。

In a linked list of size n, where n is even, the

i^{th}

$i^{t h}$ node (0-indexed) of the linked list is known as the twin of the

/**
 * 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;
}