2130. Maximum Twin Sum of a Linked List

解題思路

題目要求兩兩對應點和的最大值。要能找到一個點的對應點，就要能找到中間在哪。

在 linked list 中找中間，可以用 two pointer。

再來觀察 two pointer，當 linked list 是偶數長度時，slow pointer 會一一走訪左半部的 node，停在中間靠右的 node。

所以可以在找中間點的同時，用 stack 紀錄點的數值。當找到中間點時，一個個 pop 出來跟當前的 node value 相加，看看是不是最大值。

程式碼

class Solution {
public:
    int pairSum(ListNode* head) {
        ListNode *slow, *fast;
        fast = slow = head;

        stack<int> st;
        int maxSum = 0;
        while(fast && fast->next)
        {
            st.push(slow->val);
            slow = slow->next;
            fast = fast->next->next;
        }
        while(slow)
        {     
            maxSum = max(maxSum, slow->val + st.top());
            st.pop();
            slow = slow->next;
        }
        return maxSum;
    }
};