解决链表最大孪生和问题遇内存超限，求Java优化方案

问题描述 #

在长度为n（n为偶数）的链表中，若0 ≤ i ≤ (n/2)-1，则第i个节点（0索引）是第(n-1-i)个节点的孪生节点。例如，当n=4时，节点0是节点3的孪生节点，节点1是节点2的孪生节点。这是n=4时仅有的孪生节点对。孪生和定义为一个节点与其孪生节点的数值之和。给定一个偶数长度链表的头节点head，返回该链表的最大孪生和。

代码问题分析 #

触发内存超限的核心原因是链表遍历死循环：在while(current != null)循环里，没有移动current指针（缺少current = current.next），导致程序不断将同一个节点的值重复添加到ArrayList中，最终ArrayList无限扩容耗尽内存。

除此之外还有逻辑错误：你用sum = sum + temp.get(i) + temp.get(n - i - 1)累加所有孪生对的总和，而题目要求的是单个孪生对和的最大值，这个逻辑会导致结果错误。

修复后的O(n)空间代码 #

先修复上述两个问题，用ArrayList的方案可以正常通过：

class Solution {
    public int pairSum(ListNode head) {
        ArrayList<Integer> temp = new ArrayList<>();
        ListNode current = head;
        // 修复：遍历链表时移动指针
        while(current != null){
            temp.add(current.val);
            current = current.next;
        }
        int n = temp.size();
        int maxSum = 0;
        // 修复：计算每一对的和，更新最大值
        for(int i = 0; i < n/2; i++){
            int currentSum = temp.get(i) + temp.get(n - i - 1);
            maxSum = Math.max(currentSum, maxSum);
        }
        return maxSum;
    }
}

优化为O(1)空间的方案（更优） #

如果想进一步降低空间复杂度，可以用快慢指针找到链表中点，反转后半部分链表，然后同时遍历前半部分和反转后的后半部分，计算每对的和并记录最大值：

class Solution {
    public int pairSum(ListNode head) {
        // 快慢指针找中点
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 反转后半部分链表
        ListNode prev = null;
        ListNode curr = slow;
        while(curr != null){
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        // 计算最大孪生和
        int maxSum = 0;
        ListNode firstHalf = head;
        ListNode secondHalf = prev;
        while(secondHalf != null){
            int currentSum = firstHalf.val + secondHalf.val;
            maxSum = Math.max(currentSum, maxSum);
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }
        return maxSum;
    }
}

这个方案不需要额外存储所有节点值，空间复杂度为O(1)，时间复杂度仍为O(n)，更适合处理超大链表的情况。

内容的提问来源于stack exchange，提问作者Apoorva Walia