链表最大孪生和 图解题解

这道题到底在问什么

输入

head=[5,4,2,1]

输出

6

输入

head=[4,2,2,3]

输出

7

最优解：一步一步想明白

1. 3记住「找中点 → 反转后半 → 左右对着加」,下面逐帧套它。关键在第二步:反转之后,原本的尾节点就跑到了后半段的最前面,正好和头节点配成第一对孪生。
2. 4第一步找中点。slow 和 fast 都从头节点(下标 0,值 5)出发。接下来 fast 每轮走两步、slow 每轮走一步。
3. 5看 fast(下标 0,值 5):它和它的 next 都还在,说明还没到尾,可以再走一轮。
4. 6走一轮:slow 前进一步到下标 1(值 4);fast 前进两步到 下标 2(值 2)。
5. 7看 fast(下标 2,值 2):它和它的 next 都还在,说明还没到尾,可以再走一轮。
6. 8走一轮:slow 前进一步到下标 2(值 2);fast 前进两步到 下标 4(值 6)。
7. 9看 fast(下标 4,值 6):它和它的 next 都还在,说明还没到尾,可以再走一轮。
8. 10走一轮:slow 前进一步到下标 3(值 3);fast 前进两步到 (已越过链尾)。
9. 11fast 已经越过链尾,循环停下。此刻 slow 停在下标 3(值 3),它正好是后半段的第一个节点。于是链一分为二:前半 [5, 4, 2]、后半 [3, 6, 1]。
10. 12第二步反转后半段。准备一个 prev,先置为空;cur 从后半段头(下标 3,值 3)开始。接下来一个个把箭头掉头。
11. 13第 1 步:先记住 cur(下标 3,值 3)的后继是 下标 4(值 6),再把 cur.next 掉头指向 prev(空)。它现在是反转后的尾。
12. 14第 2 步:先记住 cur(下标 4,值 6)的后继是 下标 5(值 1),再把 cur.next 掉头指向 prev(下标 3,值 3)。
13. 15第 3 步:先记住 cur(下标 5,值 1)的后继是 空(后半段到此为止),再把 cur.next 掉头指向 prev(下标 4,值 6)。
14. 16cur 变空,后半段反转完毕:现在它是 1→6→3。反转后的头 prev 落在下标 5(值 1),也就是原链表的尾节点。它马上要和原来的头节点配成第一对孪生。
15. 17第三步求孪生和。left 从原链表头(下标 0, 值 5)、right 从反转后的头(下标 5, 值 1)出发,同步往中间走。每一步 left.val + right.val 就是一对孪生和,用 ans 记最大值,ans 先置 0。
16. 18第 1 对孪生:left=5 配 right=1,孪生和 5 + 1 = 6。比当前 ans 大,ans 更新成 6。
17. 19这一对算好了,两个指针各往中间走一步:left 到下标 1(值 4)、right 到下标 4(值 6),准备下一对。
18. 20第 2 对孪生:left=4 配 right=6,孪生和 4 + 6 = 10。比当前 ans 大,ans 更新成 10。
19. 21这一对算好了,两个指针各往中间走一步:left 到下标 2(值 2)、right 到下标 3(值 3),准备下一对。
20. 22第 3 对孪生:left=2 配 right=3,孪生和 2 + 3 = 5。没超过当前 ans=10,ans 不变。
21. 23right 走到了空,说明所有孪生对都配完了,循环停下。每一对都比较过,ans 里就是最终答案。
22. 24三对孪生和分别是 6、10、5,最大的就是 10。回头看整趟:快慢指针一遍走到中点,后半段就地反转(没开新链),再左右对着相加一遍,全程只挪了几个指针,额外空间 O(1)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import Optional, List
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        prev = None
        while slow:
            nxt = slow.next
            slow.next = prev
            prev = slow
            slow = nxt
        ans = 0
        while prev:
            ans = max(ans, head.val + prev.val)
            head = head.next
            prev = prev.next
        return ans

#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int pairSum(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
        ListNode* prev = nullptr;
        while (slow) { ListNode* nxt = slow->next; slow->next = prev; prev = slow; slow = nxt; }
        int ans = 0;
        while (prev) { ans = max(ans, head->val + prev->val); head = head->next; prev = prev->next; }
        return ans;
    }
};

import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
    public int pairSum(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
        ListNode prev = null;
        while (slow != null) { ListNode next = slow.next; slow.next = prev; prev = slow; slow = next; }
        int ans = 0;
        while (prev != null) { ans = Math.max(ans, head.val + prev.val); head = head.next; prev = prev.next; }
        return ans;
    }
}

复杂度

面试官可能追问