141、环形链表

基本思想：

使用快慢指针，如果是环形的，快指针一定会追上慢指针

具体实现：

循环让快慢指针往后跑，

循环条件是快指针不等于慢指针，

快指针等于慢指针则跳出循环

如果在循环内，快指针指向了null，

跳出循环返回不是环形链表

代码：

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False
        
        slow = head
        fast = head.next

        while slow != fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        
        return True

 

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

 

142、环形链表II

基本思想：

快慢指针

具体实现：

1、快慢指针相遇时，慢指针走了k步，快指针走了2k步

2、设相遇点到环起点距离为m

3、k-m是头结点到环起点的距离

从相遇点到环起点的距离也是k-m

4、一个指针从头结点走，一个指针从相遇点走，相遇处则是环起点

代码：

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast, slow = head, head
        while True:
            if not (fast and fast.next):
                return
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast