基本概念
快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动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
|
ListNode * RGetKthNode(ListNode * pHead, unsigned int k) { if(k == 0 || pHead == 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; } while(pAhead->next != NULL) { pBehind = pBehind->next; pAhead = pAhead->next; } return pBehind; }
|
参考文章:
快慢指针
关于快慢指针的若干应用详解
FROM :blog.cfyqy.com | Author:cfyqy
免责声明:文章中涉及的程序(方法)可能带有攻击性,仅供安全研究与教学之用,读者将其信息做其他用途,由读者承担全部法律及连带责任,本站不承担任何法律及连带责任;如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截,联系方式见首页),望知悉。
点赞
https://cn-sec.com/archives/721965.html
复制链接
复制链接
-
左青龙
- 微信扫一扫
-
-
右白虎
- 微信扫一扫
-
评论