快慢指针

admin 2022年1月6日01:37:11安全博客评论10 views1375字阅读4分35秒阅读模式

基本概念

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

例题

详情看:
快慢指针
关于快慢指针的若干应用详解

判断单链表是否为循环链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int isExitsLoop(LinkList L) {
LinkList fast, slow;
fast = slow = L;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
break;
}
}
return ((fast == NULL) || (fast->next == NULL));
}

在有序链表中寻找中位数

1
2
3
4
5
6
7
8
9
10
11
12
13
while (fast&&slow)
{
  if (fast->next==NULL)
   return slow ->data;
  else if (fast->next!= NULL && fast->next->next== NULL)
   return (slow ->data + slow ->next->data)/2;
  else
  {
   fast= fast->next;
   fast= fast->next;
   slow = slow ->next;
  }
 }

如果链表为存在环,如果找到环的入口点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
node* findLoopPort(node *head) {
node *fast, *slow;
fast = slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
break;
}
}
if ((fast == NULL) || (fast->next == NULL)) {
return NULL;
}
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;

输出链表中的倒数第K个节点(即正数第K-1个节点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 查找单链表中倒数第K个结点  
ListNode * RGetKthNode(ListNode * pHead, unsigned int k) // 函数名前面的R代表反向
{
if(k == 0 || pHead == NULL) // 这里k的计数是从1开始的,若k为0或链表为空返回NULL
return NULL;

ListNode * pAhead = pHead;
ListNode * pBehind = pHead;
for(int i=0;i<k-1;i++){
pAhead=pAhead->next;
if(pAhead==null) return null;//当链表长度小于k时候,返回Null
}
while(pAhead->next != NULL) // 前后两个指针一起向前走,直到前面的指针指向最后一个结点
{
pBehind = pBehind->next;
pAhead = pAhead->next;
}
return pBehind; // 后面的指针所指结点就是倒数第k个结点
}

参考文章:
快慢指针
关于快慢指针的若干应用详解

FROM :blog.cfyqy.com | Author:cfyqy

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月6日01:37:11
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  快慢指针 http://cn-sec.com/archives/721965.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: