LeetCode 2130. 链表最大孪生和

2026-07-14 HGNULB 约 11 分钟

文章信息 3 个分类 3 个标签

分类

题目描述

✅ 2130. 链表最大孪生和

题意分析

给一条长度为偶数的单链表，下标 i 与下标 n-1-i 互称孪生节点，两者值之和叫「孪生和」。要返回所有孪生和里的最大值。

把定义摊开看：n=4 时配对是 (0,3) 和 (1,2)，n=6 时是 (0,5)、(1,4)、(2,3)。也就是说配对方式是首尾对撞，一共恰好 n/2 对，每个节点属于且仅属于一对，不存在落单的节点 —— 这正是「n 为偶数」这条约束买来的好处。官方样例 [4,2,2,3] 的两对分别是 4+3=7 与 2+2=4，答案取 7。

难点全在数据结构上：首尾对撞在数组里就是左右两个下标相向而行，可单链表只能从头往尾单向走，下标 n-1-i 那半边根本没法反着遍历。所以真正要解决的问题不是「怎么求最大值」，而是「怎么让后半段可以从后往前被访问到」。

约束里节点数是 [2, 10^5] 中的偶数，值域 1 <= Node.val <= 10^5。前者说明 n=2（只有一对）是最小情形，且规模不允许 $O(n^2)$ 的两两枚举；后者说明孪生和最大 2 * 10^5，int 绰绰有余，不必担心溢出。另外，n 恒为偶数意味着不用考虑「正中间那个节点跟谁配对」的尴尬情况。答案初始化成 0 是安全的，因为节点值恒为正数，任何一对孪生和都严格大于 0。

解法：快慢指针找中点 + 反转后半段

核心思路

最朴素的做法是把链表整个倒进数组，然后左右双指针对撞求最大和，$O(n)$ 时间 $O(n)$ 空间；把前半段压进栈再和后半段逐个弹出配对，本质是同一件事，空间还是 $O(n)$。瓶颈很明确：额外空间只是为了买到「反向访问后半段」的能力，如果能让链表自己具备这个能力，$O(n)$ 的辅助空间就可以省掉。

关键观察是：反转一条链表只需要 $O(1)$ 额外空间。既然只有后半段需要被反着读，那就只反转后半段。反转之后，原本的尾节点变成了后半段的新头，此时从原头节点和新头节点同时往后走，第 t 步拿到的正好是下标 t 和下标 n-1-t 的两个节点 —— 首尾对撞被改造成了两条链的同向并行遍历，一条走前半段，一条走反转后的后半段。

于是问题拆成两步，第一步是找到后半段的起点。用快慢指针：slow 从 head 出发每轮一步，fast 从 head 出发每轮两步，维持不变量 —— fast 走了 2k 步时 slow 恰好走了 k 步。因为 n 是偶数，循环在 fast 变成空时结束，此时 fast 走了 n 步，slow 走了 n/2 步，slow 精确停在下标 n/2，也就是后半段的第一个节点。这里两个指针同起点是刻意的：偶数长度下同起点的快慢指针停在偏右的那个中点，正是我们要的后半段开头，不需要哨兵也不需要挪起点。

第二步反转以 slow 开头的这段链表，得到新头 prev。反转会把原来的 slow（下标 n/2）变成新链的尾并令其 next 为空，而前半段最后一个节点（下标 n/2 - 1）仍然指向它 —— 换句话说，前半段从 head 出发向后走，走到下标 n/2 就自然终止，长度刚好 n/2；反转后的后半段从 prev 出发也是 n/2 个节点。两条链等长，while (prev != null) 一个条件就能同时管住两边，配对的不变量是「第 t 次迭代拿到 a[t] 与 a[n-1-t]」。

反转是破坏性的，函数结束后链表结构已经变了。本题只要求返回一个整数、没有说要保持链表原样，所以这是可接受的代价；面试时最好主动说明这一点，并补一句「如果要求不可破坏，再反转回去即可，依然是 $O(1)$ 空间」。

解题步骤

令 slow = head、fast = head，当 fast != null && fast.next != null 时 slow 走一步、fast 走两步。为什么：二倍速让 fast 到头时 slow 只走了一半；两个判空分别拦住「已经越过尾部」和「只剩一个节点、迈不出第二步」，缺一个就会空指针。

循环结束后 slow 即下标 n/2 的节点，也就是后半段的第一个节点。为什么：n 为偶数时 fast 恰好落到空，走满 n 步，按不变量 slow 走了 n/2 步；同起点出发不需要任何偏移修正。

用 prev、next 三指针把从 slow 开始的这段链表原地反转，反转结束后 prev 是新的头（即原链表的尾节点）。为什么：反转只改指针不建新节点，是把「反向访问」这项能力换成 $O(1)$ 空间的唯一手段。

反转的同时，原下标 n/2 的节点 next 被置空，前半段因此变成一条长度为 n/2 的独立链。为什么：这让前半段的遍历自带终止条件，两条链等长，收尾时只需要一个循环条件。

从 head 和 prev 同时出发，每轮取 head.val + prev.val 更新答案，两者各走一步，直到 prev 为空。为什么：第 t 轮 head 在下标 t、prev 在下标 n-1-t，正好是一对孪生节点，n/2 轮不重不漏地覆盖全部配对。

返回累计的最大值。为什么：节点值恒为正，答案初始为 0 不会被误当成最优解。

以 [4,2,2,3] 走一遍：n=4。快慢指针第一轮，fast 的 next 是节点 2（下标 1）不为空，slow 前进到下标 1，fast 前进两步到下标 2；第二轮，fast 在下标 2、其 next 是下标 3 不为空，slow 前进到下标 2，fast 越过下标 3 变成空；第三轮判空失败退出。slow 停在下标 2，正是 4/2，后半段就是 [2,3]。反转 [2,3]：初始 prev 为空，处理节点 2 后 prev 指向它、它的 next 变空；处理节点 3 后 prev 指向节点 3、节点 3 的 next 指向节点 2。此时前半段是 4 -> 2 -> 2(已断尾)，后半段是 3 -> 2。配对循环第一轮 head.val=4、prev.val=3，和为 7，答案更新为 7；第二轮 head.val=2（下标 1）、prev.val=2（下标 2），和为 4，不更新；第三轮 prev 为空退出。返回 7，与期望一致。

n=2 边界：输入 [1,100000]。快慢指针第一轮，fast 的 next 不为空，slow 走到下标 1，fast 变空；第二轮退出。slow 停在下标 1，后半段只有一个节点，反转后 prev 仍是它、next 已被置空。配对一轮得到 1 + 100000 = 100001，第二轮 prev 为空退出，返回 100001。最小规模同样走通，不需要特判。

代码实现

class Solution {
    public int pairSum(ListNode head) {
        // 同起点快慢指针：fast 走满 n 步时 slow 恰好走 n/2 步。
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // n 为偶数，slow 精确停在下标 n/2，即后半段的第一个节点。
        ListNode prev = null;
        while (slow != null) {
            ListNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }
        // prev 是原链表的尾节点；反转顺带把前半段的尾巴断开，两段等长。
        int ans = 0;
        while (prev != null) {
            // 第 t 轮：head 在下标 t，prev 在下标 n-1-t，正好一对孪生节点。
            ans = Math.max(ans, head.val + prev.val);
            head = head.next;
            prev = prev.next;
        }
        return ans;
    }
}

func pairSum(head *ListNode) int {
    // 同起点快慢指针：fast 走满 n 步时 slow 恰好走 n/2 步。
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    // n 为偶数，slow 精确停在下标 n/2，即后半段的第一个节点。
    var prev *ListNode
    for slow != nil {
        next := slow.Next
        slow.Next = prev
        prev = slow
        slow = next
    }
    // prev 是原链表的尾节点；反转顺带把前半段的尾巴断开，两段等长。
    ans := 0
    for prev != nil {
        // 第 t 轮：head 在下标 t，prev 在下标 n-1-t，正好一对孪生节点。
        if head.Val+prev.Val > ans {
            ans = head.Val + prev.Val
        }
        head = head.Next
        prev = prev.Next
    }
    return ans
}

复杂度分析

时间复杂度：$O(n)$，找中点扫过 $n$ 个节点（fast 走满全程），反转后半段扫过 $n/2$ 个节点，配对再扫 $n/2$ 对，三段都是线性且互不嵌套，合计仍是 $O(n)$。

空间复杂度：$O(1)$，全程只用了 slow、fast、prev、next、ans 这几个变量，反转是原地改指针，没有数组、栈或递归栈，与 $n$ 无关。

关键点总结

链表不能反向遍历，就把要反向读的那一段就地反转。这是链表题把 $O(n)$ 空间压到 $O(1)$ 的通用套路：数组里的「左右对撞」在链表里等价于「反转一半后两条链同向并行」。

快慢指针的落点由起点差决定。同起点、偶数长度时慢指针停在下标 n/2（偏右中点，即后半段起点）；若像删除类题目那样需要停在前驱，就得让慢指针从哨兵出发。改起点比改循环条件更容易推理，也更不容易写错边界。

反转顺手断开的尾巴是资源不是麻烦。反转让前半段的末节点 next 变空，两段自然等长，收尾循环只需要一个判空条件；若刻意去「保护」原来的连接，反而要额外记录长度或计数。

走两步的指针必须做两次判空。fast != null 与 fast.next != null 各拦一种越界，只写一个在某类长度上必崩。

面试视角：面试官几乎一定会先接受 $O(n)$ 空间的数组或栈解法，然后追问「能不能 $O(1)$ 空间」，这时要能立刻说出「反转后半段」并解释为什么中点用同起点快慢指针就够。第二个高频追问是「链表被你改坏了怎么办」，答案是再反转回去，仍然 $O(1)$ 空间、$O(n)$ 时间 —— 主动说出这条限制比被问出来加分得多。

易错点总结

误以为慢指针要停在中点的前驱，于是从哨兵出发：慢指针停在下标 n/2 - 1，反转的那段长度变成 n/2 + 1，比前半段多一个节点。[1,9,9,1]、[4,2,2,3]、[1,2,3,4,5,6] 一律抛空指针异常 —— 配对循环以 prev 为准多跑一轮，而 head 那边早已走到空。删除类题目要前驱、本题要后半段起点，套路不能生搬。

快指针从 head.next 出发：慢指针少走一步，与上一条同样落在 n/2 - 1，[1,9,9,1]、[4,2,2,3]、[1,2,3,4,5,6] 同样全部抛空指针异常。快慢指针的起点一旦动过，落点必须重新推一遍，不能凭手感沿用别题的写法。

循环条件只写 while (fast != null)：偶数长度下 fast 会停在最后一个节点，再执行 fast.next.next 直接抛空指针异常。本题 n 恒为偶数，这条一写就是全错，连样例都过不去。

把整条链表都反转再配对：[4,2,2,3] → 输出 7，[1,2,3,4,5,6] → 输出 7，看起来都对；但 [1,9,9,1] → 输出 2，正确答案是 18。原因是整条反转后旧 head 变成了尾巴、next 为空，配对循环只跑得动一轮，实际返回的永远是 a[0] + a[n-1] 这一对。当最大孪生和恰好出现在最外层时它就是对的，样例极易全过，是本题最危险的假通过。

反转后拿 slow 当新头：反转循环退出时 slow 已经是空，配对循环一轮都不进，[1,9,9,1]、[4,2,2,3]、[1,2,3,4,5,6] 一律返回 0。新头永远是 prev，这是原地反转最常见的收尾错误。

反转时忘了先保存 slow.next：写成 slow.next = prev; slow = slow.next;，后继指针在读取之前就被覆盖，slow 立刻跳回 prev，两个节点互指形成自环，循环再也出不来。三指针反转的顺序「先存后继、再改指针、再双双前移」不能乱。

配对循环写成 while (head != null && prev != null) 当作保险：条件本身没错，但它会把上面几条起点选错导致的空指针异常静默吞掉，变成安静地输出一个错误的最大值，反而更难定位。等长是由「反转起点选在下标 n/2」保证的，不该靠循环条件补救。

配对循环里忘了让 head 前移，只推进 prev：每一轮都拿 a[0] 去和后半段的各个节点相加，结果退化成 a[0] + max(后半段)。[1,9,9,1] → 输出 10（1+9）而不是 18。两条链必须严格同步前进，配对关系才成立。

答案初始化的安全性来自值域：本题 Node.val >= 1，初始化成 0 不会被误当成最优解；一旦照搬到允许负值的变体上，0 就成了虚假下界，会返回 0 而不是真实的最大和。换题时初始值必须重新确认，别把这行当模板抄。

相似题目

题目	难度	考察点
876. 链表的中间结点	简单	只要返回中点本身，不需要反转和配对，是本题第一步的独立形态
206. 反转链表	简单	三指针原地反转的裸题，本题只把它作用在后半段而非整条链上
234. 回文链表	简单	同样是找中点 + 反转后半段 + 并行比对，收尾做的是判等而不是求最大和
2095. 删除链表的中间节点	中等	慢指针要停在中点的前驱而非中点，靠哨兵挪起点，正好反衬本题为何用同起点
143. 重排链表	中等	中点 + 反转后半段之后做的是交叉拼接，要真正改动链表结构而不只是读值