网站建设_超速云建站,wordpress4.5.3漏洞,网站页面结构,电商在线官方文章目录1. 题目2. 解题1. 题目
在一个大小为 n 且 n 为 偶数 的链表中#xff0c;对于 0 i (n / 2) - 1 的 i #xff0c;第 i 个节点#xff08;下标从 0 开始#xff09;的孪生节点为第 (n-1-i) 个节点 。
比方说#xff0c;n 4 那么节点 0 是节点 3 的孪…
文章目录1. 题目2. 解题1. 题目
在一个大小为 n 且 n 为 偶数 的链表中对于 0 i (n / 2) - 1 的 i 第 i 个节点下标从 0 开始的孪生节点为第 (n-1-i) 个节点 。
比方说n 4 那么节点 0 是节点 3 的孪生节点节点 1 是节点 2 的孪生节点。这是长度为 n 4 的链表中所有的孪生节点。
孪生和 定义为一个节点和它孪生节点两者值之和。
给你一个长度为偶数的链表的头节点 head 请你返回链表的 最大孪生和 。
示例 1
输入head [5,4,2,1]
输出6
解释
节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。
链表中没有其他孪生节点。
所以链表的最大孪生和是 6 。示例 2
输入head [4,2,2,3]
输出7
解释
链表中的孪生节点为
- 节点 0 是节点 3 的孪生节点孪生和为 4 3 7 。
- 节点 1 是节点 2 的孪生节点孪生和为 2 2 4 。
所以最大孪生和为 max(7, 4) 7 。示例 3
输入head [1,100000]
输出100001
解释
链表中只有一对孪生节点孪生和为 1 100000 100001 。提示
链表的节点数目是 [2, 10^5] 中的 偶数 。
1 Node.val 10^5来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-twin-sum-of-a-linked-list 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
快慢指针找到链表的中点断开反转后面一段链表双指针从首尾开始遍历求首尾的和
/*** Definition for singly-linked list.* 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 *fast head, *slow head, *prev NULL;while(fast fast-next){fast fast-next-next;prev slow;slow slow-next;}prev-next NULL;ListNode* end reverse(slow);int maxsum -1;while(end head){maxsum max(maxsum, end-val head-val);end end-next;head head-next;}return maxsum;}ListNode* reverse(ListNode *head){if(!head || !head-next) return head;ListNode *prev NULL, *cur head, *next NULL;while(cur){next cur-next;cur-next prev;prev cur;cur next;}return prev;}
};208 ms 113.8 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
