【LeetCode 2130】 链表最大孪生和 - 解题总结

📌 题目介绍

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

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

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

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

💡 核心思路

🔑 三步解法

步骤 1：快慢指针找中点

let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// slow 指向后半段起点

步骤 2：反转后半段链表

let prev = null, curr = slow;
while (curr !== null) {
let next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// prev 指向反转后的头

步骤 3：双指针计算最大和

let maxSum = 0;
let p1 = head, p2 = prev;
while (p2 !== null) {
let sum = p1.val + p2.val;
maxSum = Math.max(maxSum, sum);
p1 = p1.next;
p2 = p2.next;
}
return maxSum;

📊 复杂度分析

🎯 知识点总结

📚 类似题目推荐

💬 学习心得：链表题的关键是画图理解指针变化，动手模拟每一步能帮助避免逻辑错误！

完整代码

var pairSum = function(head) {
//找到链表中点(快慢指针)
let slow = head; //定义快慢指针
let fast = head;
while (fast !== null && fast.next !== null){ //确保快指针两步都有路可走
slow = slow.next; //慢指针每次指向下一个节点
fast = fast.next.next; //快指针每次指向下下个节点
}
//将后半段链表反转(三指针迭代)
let prev = null;
let curr = slow;
while(curr !== null){
let next = curr.next;// 1. 暂存下一个节点
curr.next = prev; // 2. 翻转指向
prev = curr; // 3. prev 前进到当前节点
curr = next; // 4. curr 前进到下一个节点
}
//遍历前后两段,计算最大孪生和(双指针)
let maxSum = 0;
let p1 = head;
let p2 = prev;
while (p2 !== null) {
// 计算当前孪生和并更新最大值
let currentSum = p1.val + p2.val
maxSum = Math.max(maxSum,currentSum)
// 移动两个指针
p1 = p1.next
p2 = p2.next
}
return maxSum;

};

PS：该总结由Leet生成