首页 > 其他分享 >快慢指针-小记

快慢指针-小记

时间:2023-04-03 13:45:15浏览次数:42  
标签:右移 快慢 lowPoint nil fastPoint 小记 指针

快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2,慢指针每次向前移动1次。最后,慢指针就是中位数。

这个理论,是建立在中位数 = n / 2的基础上。

同时,适用于: 单向链表查找。

这个理论,需要一个简易的规律总结即可自证。

[1, 2, 3]

lowPoint: 右移一步

fastPoint: 右移二步

终结条件判断: lowPoint.Next != nil && fastPoint.Next != nil

那么fastPoint指向到3时,循环终结,此时,慢指针为: 2.

[1, 2, 3, 4]

[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

lowPoint: 右移 8 步

fastPoint: 右移 8 * 2 步,此刻fastPoint将指向nil,循环终结。

而lowPoint,为: 8.

标签:右移,快慢,lowPoint,nil,fastPoint,小记,指针
From: https://www.cnblogs.com/supermarx/p/17282807.html

相关文章

  • 归并排序-小记
    归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(DivideandConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。类比题目:三数求和。......
  • 智能指针
    1、分析下面代码,说出问题所在#include<bits/stdc++.h>usingnamespacestd;classA{public:A(){};A(inta):age(a){};~A(){};private:intage;};intmain(){A*a=newA(10);shared_ptr<A>p1(a);shared_ptr<A>......
  • 【入门】Go语言指针详解
    目录一、指针介绍1.1什么是指针?1.2指针有什么用?二、指针的定义三、指针操作注意事项3.1空指针3.2操作没有合法指向的内存3.3new()函数使用一、指针介绍1.1什么是指针?指针是一种存储变量内存地址的变量。Go语言中的指针与C/C++中的指针类似,但是Go语言中的指针不能......
  • 走进“指针”的大门
    1、前言   指针是C语言的“精髓”,学C语言不学指针等同于C语言白学,这话语说的虽然直白,但是却真正体现出了指针在C语言中的重要性。   要想成为C语言方面的大佬,那你必须玩转指针,指针在C语言中的重要性不言而喻,但它也是我们入门C语言的拦路虎,很多大学的非计算机专业对C语......
  • 【使用小记】Debian开箱不即用之apt镜像源之配置
    安装问题首先开局就是:```Debian读取数据出错请确认您已经插入了正确的安装介质......```(我默认的是繁体:```讀取資料時發生了問題請確認是否已確實放置安裝媒體...```)处理方法①:推荐!刷入livdCD,安装时候镜像源前用工具ping一下然后看看哪个快(这个方法不会轻易出......
  • Thinkpad T14升级Windows11ver22h2失败问题解决小记
    背景手头的ThinkPad在近一年的时间里每次升级Windows11的22h2版本每次都会报错,具体有以下几种情况:更新过程中无问题,重启后黑屏更新过程中会卡在26%左右,然后蓝屏报KENERAL_CHECK_FAIL,接着便自动重启进入修复程序在WindowsUpdate更新中报错0xC1900101在上述错误出现后,再次更......
  • go 指针
    前言:变量在运行时都拥有一个地址,这个地址代表变量在内存中的位置,当一个指针被定义后没有分配到任何变量时,它的默认值为nil。Go语言中使用在变量名前面添加&操作符(前缀)来获取变量的内存地址。指针变量通常缩写为ptr。正文:通过指针,获取变量的值num:=5ptr:=&num   ......
  • 2023-03-21-将指针所在地址传入函数来创建链表的一种写法
    如下,通过将指针所在的地址传入函数中即**p的形式,来保证直接对地址进行运算,而不需要再返回一个链表//双链表#include<stdio.h>#include<stdbool.h>#include<malloc.h>typedefstructDNode{intdata;structDNode*prior,*next;//prior指向上一个结点,next指......
  • 【LBLD】双指针技巧秒杀七道数组题目
    【LBLD】双指针技巧秒杀七道数组题目快慢指针技巧classSolution{public:intremoveDuplicates(vector<int>&nums){intfast=0;intslow=0;while(fast<nums.size()){if(nums.at(fast)!=nums.at(slow)){......
  • 结构体里面定义一个该结构体类型变量为什么必须用指针
    一.错误:structTreeNode{intval;TreeNodeleft;TreeNoderight;};二.分析原因:如果在定义classA时,A域的类型是未定义的classA而不是指向classA对象的指针类型,编译器会尝试在编译时分配一块内存给A域,但由于classA的定义还没有出现,因此无法确定A域需要多......