赞
踩
快慢指针常用于判断链表中是否有环和寻找链表中值。
快慢指针的原理在于一快一慢两个指针,快指针每次移动两个节点,慢指针每次移动一个节点。
假如链表没环,那么快指针必然会先遇到空指针,即可判断链表无环。
而当链表有环时,快慢指针必然在环内循环,那么此时快慢指针就像钟表上的时针和分针,不管怎么转总有一刻会重合在一起。
可能有同学还不是特别明白。
首先有个长度为n的环,假设此时快指针在x1处,慢指针在x2处。
- 环
- -------->x1---------->---
- ^ |
- | |
- | |
- ---<-----------x2<-------
此时快指针距离慢指针 d=x1+n-x2
快指针每次移动2,慢指针每次移动1,所以快指针相对慢指针移动1,那么只需要移动 d 次快指针就能追上慢指针了。
如果还不清楚就想想钟表吧~看代码:
- struct Node{
- int val;
- Node *next;
- };
-
- //判断链表是否有环
- bool hasCircle(Node *node) {
-
- //定义快慢指针
- Node *fast=node;
- Node *slow=node;
-
- //因为快指针要走两个节点,所以要多判断一步,遇到空指针说明没有环
- while (fast != NULL && fast->ne
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。