以图明志

数据结构

[专题] 如何判断链表是否有环的存在

“快慢指针”的使用
有环的定义是,链表的尾节点指向了链接中间的某个节点。比如下图,如果单链表有环,则在遍历时,在通过结点J之后,会重新回到结点D。如何判断一个单链表是否有环呢?这个可以用昨天提到的“快慢指针”来解决吧?设两个工作指针,一个快一个慢,如果有环的话,它们会必然在某点相遇。

数据结构

用快慢指针判断单链表环,找到环入口

扩展到判断两个链表是否相交
快慢指针在解决单链表环问题的时候是非常有用的,下面来探讨一下单链表的环的一些问题。有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。

数据结构

腾讯面试题:快速找到未知长度单链表的中间节点

快慢指针在单链表中很有用处
普通的方法很简单,首先遍历一遍单链表以确定单链表的长度L。然后再次从头节点出发循环L/2次找到单链表的中间节点。算法复杂度为O(L+L/2)=O(3L/2)。能否再优化一下这个时间复杂度呢?有一个很巧妙的方法:设置两个指针*search、*mid都指向单链表的头节点。其中* search的移动速度是*mid的2倍。当*search指向末尾节点的时候,mid正好就在中间了。这也是标尺的思想。
1 / 1 首页 < Prev 1 Next > 尾页 页码: