2130. 链表最大孪生和-辅助数组存储法
2023-09-14 09:06:52 时间
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 。
博主觉得这题最直观的方法应该是直接存储数据然后求解就可以了,当然应该有其他更加复杂但效率更高的算法,解题代码如下:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
int length_list(struct ListNode* head){
int len=0;
while(head){
head=head->next;
len++;
}
return len;
}
int pairSum(struct ListNode* head){
int len=length_list(head);
int a[len];
int i=0;
while(head){
a[i++]=head->val;
head=head->next;
}
int max=a[0]+a[len-1];
for(int i=1;i<len/2;i++){
if(a[i]+a[len-i-1]>max){
max=a[i]+a[len-i-1];
}
}
return max;
}
相关文章
- LeetCode每日一题-3:回文链表
- LeetCode 21. 合并两个有序链表 题解 C++
- LeetCode19. 删除链表的倒数第 N 个结点
- 剑指offer No.55 链表中环的入口结点
- 反转链表
- 【Day 01】力扣(LeetCode)每日一刷[506.相对名次][264.丑数][23.合并N个升序链表]
- JDK1.8以后的hashmap为什么在链表长度为8的时候变为红黑树
- C++ 不知树系列之认识二叉树(数组、链表存储的实现)
- 【leetcode 206】 反转链表(简单)
- 【Android 异步操作】手写 Handler ( 消息队列 MessageQueue | 消息保存到链表 | 从链表中获取消息 )
- 【数据结构】链表
- Linux:实现链表技术的精彩实例(linux链表实例)
- 算法练习之环形链表详解编程语言
- 从Linux构建链表:实现高效数据存储(linux链表)
- Redis链表深入理解实现原理(redis链表实现原理)
- 基于Redis实现分布式链表存储(redis 链表 分布式)
- 利用Redis链表实现性能优异的数据存储(redis链表优势)
- c#自定义泛型链表类的详解