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

双指针 -876. 链表的中间结点-leetcode

开始一个专栏,写自己的博客

双指针,也算是作为自己的笔记吧!


双指针从广义上来说,是指用两个变量在线性结构上遍历而解决的问题。狭义上说,

  • 对于数组,指两个变量在数组上相向移动解决的问题;
  • 对于链表,指两个变量在链表上同向移动解决的问题,也称为「快慢指针」问题。

 

题库讨论交流


876. 链表的中间结点 - 力扣(Leetcode)

目录

方法一

方法二.滑动窗口


 

70298652c7d448eea30c31e580419f53.png

 

方法一

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode middleNode(ListNode head) {ListNode p=head;int len=0;while(p!=null){len++;p=p.next;}ListNode list=head;for(int i=0;i<len/2;i++){list=list.next;}return list;}
}

从实例中可以发现,当有五个元素的时候,返回会以第(int)5/2个节点作为头结点;当有六个元素的时候,返回会以6/2个节点作为头结点。

所以,无论链表元素个数是奇数个还是偶数个都一样。

先计算出链表一共有多少个节点,然后将第len/2个节点作为头结点返回即可。

方法二.滑动窗口

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode middleNode(ListNode head) {ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}return slow;}
}

4b41838b2bd340fcaed157496849e87a.png

 

从图中可以看出,当链表节点元素有五个的时候,需要返回的是第三个节点作为头节点,所以最终要返回的是指向第三个结点的那个指针。

在这个有五个节点的链表中,两个指针分别进行了三次移动。

每一次slow指针往后移动一位,fast指针往后移动二位,当fast==null||fast.next==null时,两个指针停止移动,这时,返回slow所指向的节点。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

http://www.lryc.cn/news/40462.html

相关文章:

  • Linux之运行级别
  • python搭建web服务器
  • 【SpringCloud】SpringCloud Feign详解
  • 更改Hive元数据发生的生产事故
  • 《Netty》从零开始学netty源码(八)之NioEventLoop.selector
  • TCP UDP详解
  • 超详细淘宝小程序的接入开发步骤
  • 【Python】正则表达式re库
  • JDK8使用Visual VM根据Dump文件排查OutOfMemoryError生产问题思路
  • 2023年网络安全比赛--网络安全事件响应中职组(超详细)
  • 【半监督学习】3、PseCo | FPN 错位对齐的高效半监督目标检测器
  • Tomcat+Servlet初识
  • ChatGPT-4 终于来了(文末附免费体验地址)
  • 【C++学习】类和对象(中)一招带你彻底了解六大默认成员函数
  • 面试——Java基础
  • JavaWeb——Request(请求)和Response(响应)介绍
  • JMeter压测文件上传接口和中文乱码
  • CSRF漏洞复现
  • Google Colab导入GitHub python项目进行运行
  • Qss样式表语法
  • 「Python 基础」异步 I/O 编程
  • 通配符的匹配很全面, 但无法找到元素 ‘tx:advice‘ 的声明
  • 响应式编程详解,带你熟悉Reactor响应式编程
  • 踩坑篇之WebSocket实现类中无法使用@Autowired注入对象
  • QT CTK插件框架 (一 下载编译)
  • 【Java版oj】day10 井字棋、密码强度等级
  • JavaScript的事件传播机制
  • 队列的定义及基本操作实现(链式)
  • 集成方法!
  • 20年程序员生涯,读了200多本技术书,挑了几本精华好书分享给大家