农业开发公司企业网站建设,建设厅注册中心网站首页,清远做网站,app客户端开发开始一个专栏#xff0c;写自己的博客
双指针#xff0c;也算是作为自己的笔记吧#xff01; 双指针从广义上来说#xff0c;是指用两个变量在线性结构上遍历而解决的问题。狭义上说#xff0c;
对于数组#xff0c;指两个变量在数组上相向移动解决的问题#xff1b;对…开始一个专栏写自己的博客
双指针也算是作为自己的笔记吧 双指针从广义上来说是指用两个变量在线性结构上遍历而解决的问题。狭义上说
对于数组指两个变量在数组上相向移动解决的问题对于链表指两个变量在链表上同向移动解决的问题也称为「快慢指针」问题。题库讨论交流 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 phead;int len0;while(p!null){len;pp.next;}ListNode listhead;for(int i0;ilen/2;i){listlist.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 fasthead;ListNode slowhead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;}return slow;}
} 从图中可以看出当链表节点元素有五个的时候需要返回的是第三个节点作为头节点所以最终要返回的是指向第三个结点的那个指针。
在这个有五个节点的链表中两个指针分别进行了三次移动。
每一次slow指针往后移动一位fast指针往后移动二位当fastnull||fast.nextnull时两个指针停止移动这时返回slow所指向的节点。
