LeetCode 2130. 链表最大孪生和

约 5 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 中等 LeetCode 75
标签
双指针 栈 链表

题目描述

✅ 2130. 链表最大孪生和

image-20260928234442019

image-20260928234442020

题意分析

链表长度是正偶数，下标 i 与 n - 1 - i 的两个节点互为孪生节点。需要计算首尾对称的每一对节点值之和，返回其中的最大值。

总共只有 n / 2 对，不是任选两个节点，也不需要把每一对重复统计。题目保证节点值为正，所以最大和可以从零开始更新；当前实现通过原地反转后半段完成计算，会改变原链表结构。

解法：找中点、反转后半段后计算孪生和

核心思路

[!blue]

前半段需要从头向中间访问，后半段却需要从尾向中间访问，单链表无法直接反向走。将后半段反转，就能让两条指针都沿 next 前进，同时取得首尾对称的位置。

先让快慢指针都从头开始，分别每轮走两步和一步。长度为偶数时，快指针走完全部 n 步，慢指针刚好走到下标 n / 2，也就是后半段的第一个节点，不会把前半段节点反转进去。

从慢指针位置开始反转，每次先保存原后继，再将当前 next 指向已反转部分，最后推进两个指针。反转后 prev 指向原尾节点，整段顺序变为原下标 n - 1、n - 2，直到 n / 2。

从原头和 prev 同步前进，第 t 轮分别访问原下标 t 与 n - 1 - t，恰好是一对孪生节点。以后半段是否结束控制循环，正好执行 n / 2 次。虽然原前半段尾部仍连着原中点，但比较会在走出前半段之前结束，不需要为了统计额外断链。

解题步骤

  1. 快慢指针同从头开始，在快指针及其后继存在时，分别前进两步和一步。
  2. 慢指针停在后半段头，从这里开始原地反转，改写连接前先保存原后继。
  3. 原头指针与反转后头指针同步移动，逐对相加并更新最大值。
  4. 反转后的半条链结束时停止，返回最大孪生和。

代码实现

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

        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
    }
    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)$，找中点、反转半条链和成对统计均为线性扫描。
  • 空间复杂度：$O(1)$，只保存固定数量的指针与最大值，没有数组或递归栈。

关键点总结

[!green]

  • 后半段反转，将首尾相向访问转成两条链同向前进。
  • 偶数长度与快慢同起点保证后半段入口准确位于 n / 2。
  • 反转短链的长度决定比较次数，每轮原下标之和始终为 n - 1。
  • 本实现只返回统计值，不恢复被反转的连接。

易错点总结

[!yellow]

  • 中点规则选成前半段最后节点，并从它开始反转，会破坏配对区间。
  • 改写 next 后才读取原后继，剩余节点的入口已经丢失。
  • 一直遍历原头直到空，原链没有显式断成独立前半段，可能超出需要比较的范围。
  • 每轮只移动一侧指针，不能保持首尾孪生位置对应。
  • 将本题按奇数长度链表设计额外配对规则，题目给定的偶数前提已明确中间没有单独节点。

相似题目

题目 难度 关联与区别
234. 回文链表 简单 同样找中点并反转后半段，原题比较对应值是否相等，本题求对应值和的最大值。
143. 重排链表 中等 同样把首尾节点对齐，原题继续交错重连，本题只做成对统计。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/95089892
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！