【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; 复杂度分析类型复杂度说明时间O(n)遍历链表约 1.5 次空间O(1)只使用指针变量 知识点总结快慢指针找中点/检测环的经典技巧原地反转链表三指针迭代法双指针遍历同时处理两段数据结构链表分割思想将问题拆分为独立子问题 类似题目推荐题目考点141. 环形链表快慢指针206. 反转链表链表反转143. 重排链表中点 反转 合并学习心得链表题的关键是画图理解指针变化动手模拟每一步能帮助避免逻辑错误完整代码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生成