2130.链表最大孪生和：转数组 / 快慢指针+链表翻转（O(1)）

【LetMeFly】2130.链表最大孪生和：转数组 / 快慢指针+链表翻转（O(1)）

力扣题目链接：https://leetcode.cn/problems/maximum-twin-sum-of-a-linked-list/

在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。

• 比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。

孪生和 定义为一个节点和它孪生节点两者值之和。

给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。

 

示例 1：

输入：head = [5,4,2,1]
输出：6
解释：
节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。
链表中没有其他孪生节点。
所以，链表的最大孪生和是 6 。

示例 2：

输入：head = [4,2,2,3]
输出：7
解释：
链表中的孪生节点为：
- 节点 0 是节点 3 的孪生节点，孪生和为 4 + 3 = 7 。
- 节点 1 是节点 2 的孪生节点，孪生和为 2 + 2 = 4 。
所以，最大孪生和为 max(7, 4) = 7 。

示例 3：

输入：head = [1,100000]
输出：100001
解释：
链表中只有一对孪生节点，孪生和为 1 + 100000 = 100001 。

 

提示：

• 链表的节点数目是 [2, 105] 中的 偶数 。
• 1 <= Node.val <= 105

解题方法一：转数组

遍历一遍链表，并且把链表中的每一个元素放入数组中。

使用两个指针分别指向数组中第一个和最后一个元素，当左指针在右指针之前时，不断更新答案最大值并靠近两指针。

• 时间复杂度$O(n)$，其中$n$是链表中节点数量
• 空间复杂度$O(n)$

AC代码

C++

/*
 * @LastEditTime: 2026-06-14 21:48:39
 */
class Solution {
public:
    int pairSum(ListNode* head) {
        int ans = 0;
        vector<int> vals;
        while (head) {
            vals.push_back(head->val);
            head = head->next;
        }
        for (int l = 0, r = vals.size() - 1; l < r; l++, r--) {
            ans = max(ans, vals[l] + vals[r]);
        }
        return ans;
    }
};

解题方法二：快慢指针+链表翻转

这道题可以变成两道题的组合再加一点。

第一道题 —— 快慢指针确定链表中间节点：

两个指针初始时都指向第一个节点，慢指针每次右移一个节点快指针每次右移两个，当快指针为空时即说明慢指针指向了中间节点（偏右一个）。

第二道题 —— 链表翻转：

将后半部分的链表翻转，使用三个指针分别指向上一个节点、当前节点、下一个节点，遍历一遍链表并：将当前节点的next指向上一个节点、将当前节点赋值为下一个节点、将上一个节点赋值为当前节点，直至当前节点为空时停止。

再加一点：

同时遍历前后两个链表，若前面链表指针指到了后半段链表则停止遍历。

遍历过程中更新答案最大值。

What’s more：

由于本题是在后半段链表开始翻转的，所以实际上后半段链表的第一个元素的next没有被修改过的话，会形成环。这样力扣在尝试delete链表的时候就会RE。

我们可以在翻转完后半段链表后将翻转过的链表最后一个节点(即为原始链表中后半段的第一个节点)的next置空。

• 时间复杂度$O(n)$，其中$n$是链表中节点数量
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-06-14 22:51:59
 */
/*
1 2
  | |

1 2 3 4
  | |
    |   |
*/
class Solution {
public:
    int pairSum(ListNode* head) {
        ListNode* slow = head, *fast = head;
        while (fast) {
            fast = fast->next->next;  // 因为链表是偶数个节点，所以fast->next一定非null
            slow = slow->next;
        }

        ListNode* last = slow;
        for (ListNode* now = last->next; now; ) {
            ListNode* next = now->next;
            now->next = last;
            last = now;
            now = next;
        }
        slow->next = nullptr;

        int ans = 0;
        ListNode* p1 = head, *p2 = last;
        while (p1 != slow) {
            ans = max(ans, p1->val + p2->val);
            p1 = p1->next, p2 = p2->next;
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源