快慢指针总结

快慢指针

所谓「快慢指针」是指设定两个指针,其中快的指针的移动速度是慢的指针的移动速度的两倍;“快慢指针”方法主要用来解决两类问题,即“判断一个链表是否为循环链表”以及“寻找一个有序链表的中位数”

判断一个链表是否为循环链表

思路: 当我们在遍历链表的时候,我们设计两个指针,分别是快指针和慢指针,块指针每次走2步,而慢指针每次走1步,这样的话在当我们两个指针在链表中,如果会第二次相遇则说明这里面的链表是环形链表。

publicbooleanhasRing() {

if(head !=null&& size > 0) {

Node<T> fastTemp = head, lowTemp = head;

while(lowTemp.getNext() !=null&& fastTemp.getNext() !=null) {

fastTemp = fastTemp.getNext().getNext();

lowTemp = lowTemp.getNext();

if(lowTemp == fastTemp) {

return true;

}

}

}

return false;

}

假设: 快慢指针在C点相遇,那么相遇点在离循环点B之间是x 那么头节点A离B的距离为 k 

在相遇的时候

慢指针:K + X + n*(X+Y) = m;   ①

X+Y 绕环一圈的距离;n 慢指针 总共绕了几圈在环内

快指针: 

快指针是慢指针 速度的2倍,当它们相遇时 所用的时间是一样的。那么快指针 走过得距离是2*m;

K+X +N*(X+Y) = 2*m;   ②

N为快指针绕过得圈数

将 ② - ①  得到下面公式

(N-n)*(X+Y) = m;

接下将 ① 代入 上式得到

 (N-n)*(X+Y) = K+X+n*(X+Y);

这里X+Y 环长是个定值。 假设环长为M

(N-n)*M = K+X+n*M; ---- > 得出变形得到 K+X = (N-2*n)*M ;

公式 :K+X = (N-2*n)*M  

由于我们设计的是O型循环链表,那么 起始就是循环点B上,则(N-2*n)*M = 0。

N = 2*n;  相遇时 快慢指针所绕 环的圈数 前者是后者的2倍,所用时间相同。这里跟环有多少节点没有关系。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容