首页 > 编程学习 > 链表的快慢指针

链表的快慢指针

发布时间:2022/5/14 18:55:48

参考:https://www.jianshu.com/p/21b4b8d7d31b

快慢指针:

定义两根指针,移动速度一快一慢,制造一个差值,利用这个差值来找到链表上相应的节点。
找中间值:
定义两个指针a,b。我们假设b的速度是a的两倍,a,b一起跑,那么在b遍历完链表后,a所在的位置就是链表的中间节点。
如下:
在这里插入图片描述
判断链表中是否有环:
设置两个不同速度的指针,如果在某个时刻,两指针相遇,那么链表中就存在环。
删除倒数第n个节点
就相当于要找出待删除元素前一个元素,为第n-1个节点。
首先让fast指针比slow指针快n+1个元素,当fast指针走完时,slow刚好在第n-1个元素上。

Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000