当前位置: 首页 > news >正文

每日一题(LeetCode)----链表--链表最大孪生和

每日一题(LeetCode)----链表–链表最大孪生和

1.题目(2130. 链表最大孪生和)

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

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

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

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

    示例 1:

    img

    输入:head = [5,4,2,1]
    输出:6
    解释:
    节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。
    链表中没有其他孪生节点。
    所以,链表的最大孪生和是 6 。
    

    示例 2:

    img

    输入:head = [4,2,2,3]
    输出:7
    解释:
    链表中的孪生节点为:
    - 节点 0 是节点 3 的孪生节点,孪生和为 4 + 3 = 7 。
    - 节点 1 是节点 2 的孪生节点,孪生和为 2 + 2 = 4 。
    所以,最大孪生和为 max(7, 4) = 7 。
    

    示例 3:

    img

    输入: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 length1=0;ListNode* Temp=head;while(Temp){length1++;Temp=Temp->next;}int length2=length1/2;int t=length2;Temp=head;while(t--){Temp=Temp->next;}ListNode* head2=NULL;ListNode* na=Temp;ListNode* duan=Temp->next;while(duan){na->next=head2;head2=na;na=duan;duan=duan->next;}na->next=head2;head2=na;int res=-1;for(int i=0;i<length2;i++){res=max(head->val+head2->val,res);head=head->next;head2=head2->next;}return res;}
};

思路二的代码

class Solution {
public:int pairSum(ListNode* head) {ListNode* fast=head;ListNode* slow=head;while(fast){slow=slow->next;fast=fast->next->next;}ListNode* head2=NULL;ListNode* na=slow;ListNode* duan=slow->next;while(duan){na->next=head2;head2=na;na=duan;duan=duan->next;}na->next=head2;head2=na;int res=-1;while(head2){res=max(head->val+head2->val,res);head2=head2->next;head=head->next;}return res;}
};

相关文章:

  • CANdelaStudio 使用教程3 新建Service
  • 微机原理_3
  • FileReader与URL.createObjectURL实现图片、视频上传预览
  • elasticsearch 7安装
  • css中flex两列布局(一列自适应其他固定)
  • 专业远程控制如何塑造安全体系?向日葵“全流程安全闭环”解析
  • 基于 STM32Cube.AI 的嵌入式人脸识别算法实现
  • Flink-简介与基础
  • docker 部署hbase 并且java Api连接
  • Nginx安装与配置、使用Nginx负载均衡及动静分离、后台服务部署、环境准备、系统拓扑图
  • spark的算子
  • Web3与Web3.0: Web3指的是去中心化和基于区块链的网络,Web3.0指的是链接或语义网络。
  • 讲述 什么是鸿蒙 为什么需要鸿蒙 为什么要学习鸿蒙
  • 网络攻击的常见手段
  • DataFunSummit:2023年现代数据栈技术峰会-核心PPT资料下载
  • 实现windows 窗体的自己画,网上摘抄的,学习了
  • [NodeJS] 关于Buffer
  • 《Java编程思想》读书笔记-对象导论
  • 【347天】每日项目总结系列085(2018.01.18)
  • Angular6错误 Service: No provider for Renderer2
  • Git 使用集
  • javascript 哈希表
  • Lsb图片隐写
  • Perseus-BERT——业内性能极致优化的BERT训练方案
  • php ci框架整合银盛支付
  • Promise面试题2实现异步串行执行
  • Redis 中的布隆过滤器
  • UEditor初始化失败(实例已存在,但视图未渲染出来,单页化)
  • windows下如何用phpstorm同步测试服务器
  • 分类模型——Logistics Regression
  • 力扣(LeetCode)22
  • 前端_面试
  • 全栈开发——Linux
  • 深入 Nginx 之配置篇
  • 什么软件可以剪辑音乐?
  • 小程序01:wepy框架整合iview webapp UI
  • 仓管云——企业云erp功能有哪些?
  • 曜石科技宣布获得千万级天使轮投资,全方面布局电竞产业链 ...
  • # 计算机视觉入门
  • #WEB前端(HTML属性)
  • #传输# #传输数据判断#
  • #我与Java虚拟机的故事#连载01:人在JVM,身不由己
  • (11)MSP430F5529 定时器B
  • (14)目标检测_SSD训练代码基于pytorch搭建代码
  • (JS基础)String 类型
  • (k8s中)docker netty OOM问题记录
  • (附程序)AD采集中的10种经典软件滤波程序优缺点分析
  • (三)mysql_MYSQL(三)
  • (十一)JAVA springboot ssm b2b2c多用户商城系统源码:服务网关Zuul高级篇
  • (一)搭建springboot+vue前后端分离项目--前端vue搭建
  • (转)es进行聚合操作时提示Fielddata is disabled on text fields by default
  • ***利用Ms05002溢出找“肉鸡
  • .NET Framework 的 bug?try-catch-when 中如果 when 语句抛出异常,程序将彻底崩溃
  • .net/c# memcached 获取所有缓存键(keys)
  • .net图片验证码生成、点击刷新及验证输入是否正确