做别人一样的网站,网站开始怎么做的,个人免费网站申请,佛山网站建设的公司每日一题(LeetCode)----链表–链表最大孪生和
1.题目#xff08;2130. 链表最大孪生和#xff09; 在一个大小为 n 且 n 为 偶数 的链表中#xff0c;对于 0 i (n / 2) - 1 的 i #xff0c;第 i 个节点#xff08;下标从 0 开始#xff09;的孪生节点为第 (n…每日一题(LeetCode)----链表–链表最大孪生和
1.题目2130. 链表最大孪生和 在一个大小为 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, 105] 中的 偶数 。1 Node.val 105
2.解题思路
思路一
将链表的后一半进行反转然后将链表的前一半和后一半进行相加通过比较得到结果
1.找到链表的后一半的起始节点
我们先计算出整个链表的长度然后用一个指针指向链表表头向后走整个链表的一半长度得到链表后一半的表头
2.进行反转
通过头拿断这三个指针实现反转
3.定义一个存结果的变量将反转后的后一半链表与原链表的前一半进行相加这里思路一和思路二实现方式不一样但是都差不多然后每求出一个值就和存结果的变量进行比较如果大于就把存结果的变量进行更新如果不大于就不进行更新
思路二思路二和思路一一样就是实现的方法不同
1.找到链表的后一半的起始节点
我们使用快慢指针找出后一半部分的起始节点。我们用慢指针和快指针同时指向 头节点然后我们每次将慢指针向后移动一个节点同时快指针向后移动两个节点。当 快指针指向空结点时慢指针就刚好指向链表了后一半部分的首节点
2.进行反转
通过头拿断这三个指针实现反转
3.定义一个存结果的变量将反转后的后一半链表与原链表的前一半进行相加这里思路一和思路二实现方式不一样但是都差不多然后每求出一个值就和存结果的变量进行比较如果大于就把存结果的变量进行更新如果不大于就不进行更新
3.写出代码
思路一的代码
class Solution {
public:int pairSum(ListNode* head) {int length10;ListNode* Temphead;while(Temp){length1;TempTemp-next;}int length2length1/2;int tlength2;Temphead;while(t--){TempTemp-next;}ListNode* head2NULL;ListNode* naTemp;ListNode* duanTemp-next;while(duan){na-nexthead2;head2na;naduan;duanduan-next;}na-nexthead2;head2na;int res-1;for(int i0;ilength2;i){resmax(head-valhead2-val,res);headhead-next;head2head2-next;}return res;}
};思路二的代码
class Solution {
public:int pairSum(ListNode* head) {ListNode* fasthead;ListNode* slowhead;while(fast){slowslow-next;fastfast-next-next;}ListNode* head2NULL;ListNode* naslow;ListNode* duanslow-next;while(duan){na-nexthead2;head2na;naduan;duanduan-next;}na-nexthead2;head2na;int res-1;while(head2){resmax(head-valhead2-val,res);head2head2-next;headhead-next;}return res;}
};
