Leetcode每日一题 —— 2130. 链表最大孪生和

思路

首先容易想到的是可以用快慢指针，把链表用一趟扫描截成两半。用栈来存储翻转后的前半段链表然后进行成对求和。

进一步，可以不需要线性额外空间，原地用头插法构造前半段链表翻转后的链表即可。

代码

链栈（常数额外空间）：

class Solution {

public:

    int pairSum(ListNode* head) {

        // 链表节点数为偶数

        // 快慢指针找中间点

        ListNode *slow=head,*fast=head;

        ListNode *rev=nullptr; // 前半段逆转的链表

        while(fast!=nullptr){

            ListNode* sNext=slow->next;

            ListNode* fNext=fast->next;

            slow->next=rev; // 头插法构成栈

            rev=slow;

            slow=sNext;

            fast=fNext;

            if(fast!=nullptr){

                fast=fast->next;

            }

        }

        int res=0;

        while(slow!=nullptr){

            res=max(res,rev->val+slow->val);

            rev=rev->next;

            slow=slow->next;

        }

        return res;

    }

};

用了线性额外空间：

class Solution {

public:

    int pairSum(ListNode* head) {

        // 链表节点数为偶数

        // 快慢指针找中间点

        ListNode *slow=head,*fast=head;

        vector<int> stk;

        while(fast!=nullptr){

            stk.emplace_back(slow->val);

            slow=slow->next;

            fast=fast->next;

            if(fast!=nullptr){

                fast=fast->next;

            }

        }

        int res=0;

        while(slow!=nullptr){

            res=max(res,stk.back()+slow->val);

            stk.pop_back();

            slow=slow->next;

        }

        return res;

    }

};