当前位置: 首页 > 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资料下载
  • “寒冬”下的金三银四跳槽季来了,帮你客观分析一下局面
  • 【挥舞JS】JS实现继承,封装一个extends方法
  • Angular Elements 及其运作原理
  • avalon2.2的VM生成过程
  • create-react-app项目添加less配置
  • Java Agent 学习笔记
  • leetcode讲解--894. All Possible Full Binary Trees
  • MySQL几个简单SQL的优化
  • Python_网络编程
  • RxJS: 简单入门
  • 初识 webpack
  • 从地狱到天堂,Node 回调向 async/await 转变
  • 记录一下第一次使用npm
  • 前端_面试
  • 手机端车牌号码键盘的vue组件
  • 小程序、APP Store 需要的 SSL 证书是个什么东西?
  • 自制字幕遮挡器
  • gunicorn工作原理
  • ​Base64转换成图片,android studio build乱码,找不到okio.ByteString接腾讯人脸识别
  • ​软考-高级-系统架构设计师教程(清华第2版)【第20章 系统架构设计师论文写作要点(P717~728)-思维导图】​
  • ​业务双活的数据切换思路设计(下)
  • #《AI中文版》V3 第 1 章 概述
  • #每日一题合集#牛客JZ23-JZ33
  • ()、[]、{}、(())、[[]]命令替换
  • (02)Hive SQL编译成MapReduce任务的过程
  • (C)一些题4
  • (C++17) optional的使用
  • (delphi11最新学习资料) Object Pascal 学习笔记---第5章第5节(delphi中的指针)
  • (仿QQ聊天消息列表加载)wp7 listbox 列表项逐一加载的一种实现方式,以及加入渐显动画...
  • (六)c52学习之旅-独立按键
  • (幽默漫画)有个程序员老公,是怎样的体验?
  • (转)eclipse内存溢出设置 -Xms212m -Xmx804m -XX:PermSize=250M -XX:MaxPermSize=356m
  • (轉貼) 寄發紅帖基本原則(教育部禮儀司頒布) (雜項)
  • .“空心村”成因分析及解决对策122344
  • .NET C#版本和.NET版本以及VS版本的对应关系
  • .NET Compact Framework 3.5 支持 WCF 的子集
  • .NET Framework 3.5中序列化成JSON数据及JSON数据的反序列化,以及jQuery的调用JSON
  • .NET/C# 如何获取当前进程的 CPU 和内存占用?如何获取全局 CPU 和内存占用?
  • .NET项目中存在多个web.config文件时的加载顺序
  • @DateTimeFormat 和 @JsonFormat 注解详解