快慢指针即我们有两个及以上的指针,我们可以通过控制其步长去实现某种行为。
下图中自定义的名词解释如下:
- 目标节点:要找的节点,倒数第4个。
- 目标对称点:和目标节点对称的节点,正数第4个。
- 慢指针:最后要指向目标节点的指针。
- 快指针:用于定位慢指针。
1. 找出链表中倒数第N个节点
N=4
,也就是找出链表中倒数第4个节点。初始化状态如上图。
目标对称点(也就是正数第N个节点)
,慢指针不动。
同时向后移动
,直到快指针指向最后一个节点(也就是快指针指向节点的next为null),这个时候慢指针指向的正好是倒数第4个节点。
2. 找出链表的中间节点
当快指针指向最后一个节点时,慢指针指向的正好是快指针的一半(也就是中间节点)
3. 检测链表中是否存在循环
链表初始状态如上图。
只要快指针进入循环中,就会一直绕圈,而慢指针迟早也会进入循环中,所以快慢指针一定会相遇,
只要快指针和慢指针相遇就说明该链表中存在循环
。
当然,你也可以把链表中的数据存放到Map/Set中,当该节点已经存在,就说明有循环。时间复杂度为O(n),但是空间复杂度也是O(n)。使用双指针时,快指针可能会在循环中绕几圈(这取决于你的快指针的步长),但是空间复杂度为0
。