基本概念
快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动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
评论