双指针 -876. 链表的中间结点-leetcode
创始人
2025-05-29 19:47:31

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

双指针，也算是作为自己的笔记吧！

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

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

题库讨论交流

876. 链表的中间结点 - 力扣（Leetcode）

目录

方法一

方法二.滑动窗口

方法一

/*** 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

从实例中可以发现，当有五个元素的时候，返回会以第(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;}
}

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

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

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

上一篇：第一批痴迷中古的年轻人，已经袪魅了

下一篇：持续改进与回归

相关内容

热门资讯

原创 停... 在波斯湾的局势中，本以为和平的曙光即将降临，却谁知这不过是特朗普与以色列的又一场政治戏码。面对美以的...
创业板指跳空大涨近4%，再创近... 4月10日，创业板指跳空高开，收涨3.8%，盘中一度创下近4年新高，创业板ETF易方达（159915...
今年第4号台风“森拉克”生成 ... 今年第4号台风“森拉克”（热带风暴级）的中心今天（10日）上午位于美国关岛东南方向约820公里的西北...
“为啥还不给白宫打电话”，澳前... 【文/观察者网 柳白】 中东战火未熄、美伊和谈在即，澳大利亚政坛却因一场“参战之争”吵了起来。 ...
X平台的货币化计划因监管障碍与... 9月4日消息，埃隆·马斯克旗下X平台的货币化计划因监管障碍与人员流失受阻。（广角观察）