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

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

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

---

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

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

 

题库讨论交流

---

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<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;}
}

 

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

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

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