快慢指针（找未知长度链表的中间、判断链表是否是循环链表）

心已赠人 2022-05-17 02:07 122阅读 0赞

`快慢指针也是一个可以用于很多问题的技巧。所谓快慢指针中的快慢指的是指针向前移动的步长，每次移动的步长较大即为快，步长较小即为慢，常用的快慢指针一般是在单链表中让快指针每次向前移动2，慢指针则每次向前移动1。快慢两个指针都从链表头开始遍历，于是快指针到达链表末尾的时候慢指针刚好到达中间位置，于是可以得到中间元素的值。快慢指针在链表相关问题中主要有两个应用：`

*  快速找出未知长度单链表的中间节点 设置两个指针 \*fast、\*slow 都指向单链表的头节点，其中\*fast的移动速度是\*slow的2倍，当\*fast指向末尾节点的时候，slow正好就在中间了。
 *  判断单链表是否有环 利用快慢指针的原理，同样设置两个指针 \*fast、\*slow 都指向单链表的头节点，其中 \*fast的移动速度是\*slow的2倍。如果 \*fast = NULL，说明该单链表 以 NULL结尾，不是循环链表；如果 \*fast = \*slow，则快指针追上慢指针，说明该链表是循环链表。

代码（别人的）：

class NodeCircle:
        def __init__(self, val):
            self.val = val
            self.next = None
    
        def has_circle(self, head):
            slow = head
            fast = head
            while (slow and fast):
                fast = fast.next
                slow = slow.next
                if fast:
                    fast = fast.next
                if fast == slow:
                    break
            if fast and slow and (fast == slow):
                return True
            else:
                return False