首页 > 其他分享 >快慢指针

快慢指针

时间:2022-09-03 16:00:44浏览次数:85  
标签:快慢 结点 中位数 链表 移动 指针

百度百科:快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2,慢指针每次向前移动1次。

判断单链表是否为循环链表 让快慢指针从链表头开始遍历,快指针向前移动两个位置,慢指针向前移动一个位置;如果快指针到达NULL,说明链表以NULL为结尾,不是循环链表。如果 快指针追上慢指针,则表示出现了循环。 在有序链表中寻找中位数 该方法在不借助计数器变量实现寻找中位数的功能。原理是:快指针的移动速度是慢指针移动速度的2倍,因此当快指针到达链表尾时,慢指针到达中点。程序还要考虑链表结点个数的奇偶数因素,当快指针移动x次后到达表尾(1+2x),说明链表有奇数个结点,直接返回慢指针指向的数据即可。如果快指针是倒数第二个结点,说明链表结点个数是偶数,这时可以根据“规则”返回上中位数或下中位数或(上中位数+下中位数)的一半。  

深入理解快慢指针算法 -- 链表环路检测

https://zhuanlan.zhihu.com/p/361049436

标签:快慢,结点,中位数,链表,移动,指针
From: https://www.cnblogs.com/uacs2024/p/16652829.html

相关文章

  • Go语言 指针详解
    现在就开始你的Go语言学习之旅吧!人生苦短,let’sGo.指针是一个代表着某个内存地址的值,这个内存地址往往是在内存中存储的另一个变量的值的起始位置.Go语言对指针的......
  • c++中面向对象以及新特性的困惑与思考【八】【指针】
    部分指针内容已经在内存相关中提及最近一些C语言的笔试题或者是面试题又屡屡出现因此在这里特地专开一栏用于强调参考书籍:《C专家编程》、《C语言与指针》、《C安全手册......
  • 116. 填充每个节点的下一个右侧节点指针
    116.填充每个节点的下一个右侧节点指针给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:structNode{intval;Node*l......
  • 指针函数和函数指针(C语言)
    @目录指针函数函数指针指针函数指针函数就是指针型函数,该函数返回一个地址。#include<stdio.h>//指针函数*point_fuc()int*point_fuc(inta,intb,int*sum){......
  • 【C++】智能指针
    这篇讲得很好https://blog.csdn.net/sjp11/article/details/123899141?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166201751616781790748003%2522%252C%2......
  • 数组&指针
    分类inta;int*a;int**a;inta[10];int*a[10];int(*a)[10];//一个指向有10个整型数数组的指针int(*a)(int);//一个指向函数的指针,该函数有一......
  • leetcode-11-双指针
    /**<p>给定一个长度为<code>n</code>的整数数组&nbsp;<code>height</code>&nbsp;。有&nbsp;<code>n</code>&nbsp;条垂线,第<code>i</code>条线的两个端点是&nbsp;<cod......
  • 前端也该刷点算法题——双指针解“链表”题也太香了叭!
    双指针解“链表”题也太香了叭!同步双指针1查找链表中倒数第k个节点剑指Offer22.链表中倒数第k个节点思路:假设链表的长度为n,不难得出倒数第k个节点即为整数第n+......
  • C语言进阶-指针的进阶
    C语言进阶之指针的进阶前言指针就是个变量,用来存放地址,地址唯一标识一块内存空间。指针的大小是固定的4/8个字节(32位平台/64位平台)。指针是有类型,指针的类型决定了指......
  • 【C++】引用与指针的区别
    安全性首先引用要比指针要安全,因为引用不能更改绑定,但是指针可以更改指向,此外指针可以有多级,但是引用一般只有一级。在使用指针的时候,我们往往需要使用断言,判断指针是不是......