思路

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

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

代码

链栈（常数额外空间）：

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

HuangXiang (YaoHuayong) 2026 年6 月 14 日 02:02 2

第一次在l站看到跟算法相关的贴,hhh，古法永远不死