所谓快慢指针中的快慢指的是指针向前移动的步长,每次移动的步长较大即为快,步长较小即为慢,常用的快慢指针一般是在单链表中让快指针每次向前移动2,慢指针则每次向前移动1。
快慢指针在提高查找性能方面的作用还是比较可观的,如以下应用:
(1)如何快速找出未知长度单链表的中间节点?
普通方法:先遍历一遍单链表确定其长度L后,再从头节点出发循环L/2次即可查找到单链表的中间节点。该问题如果采用普通的方法虽然简单,但是查找效率太低。
快慢指针:设置两个指针*fast、*slow都指向单链表的头节点,其中*fast的移动速度是*slow的2倍,当*fast指向末尾节点的时候,slow正好就在中间了,可以大大提高查找的效率。
当然,此时算法还要考虑链表结点个数的奇偶数因素,当快指针移动x次后到达表尾(1+2x),说明链表有奇数个结点,直接返回慢指针指向的数据即可。如果快指针是倒数第二个结点,说明链表结点个数是偶数,这时可以实际情况返回上中位数或下中位数或(上中位数+下中位数)的一半。
1 while (fast&&slow) 2 { 3 if (fast->next==NULL) 4 return slow ->data; 5 else if (fast->next!= NULL && fast->next->next== NULL) 6 return (slow ->data + slow ->next->data)/2; 7 else 8 { 9 fast= fast->next; 10 fast= fast->next; 11 slow = slow ->next; 12 } 13 }
(2)如何快速检测单链表是否存在循环?
利用快慢指针的原理,同样设置两个指针*fast、*slow都指向单链表的头节点,其中*fast的移动速度是*slow的2倍。如果*fast=NULL,说明该单链表以NULL结尾,不是循环链表;如果*fast=*slow,则快指针追上慢指针,说明该链表是循环链表。
1 fast=slow=head; 2 fast=fast->next->next; 3 while(true){ 4 if (fast==NULL || fast->next==NULL) 5 return false; 6 else if (fast==slow || fast->next==slow) 7 return true; 8 else{ 9 fast=fast->next->next; 10 slow=slow->next; 11 }