141. Linked List Cycle

题目描述

---

给定一个链表，判断链表中是否有环。

进阶： 你能否不使用额外空间解决此题？

最优解法——快慢指针（AC）

• 设两个指针，一个每次走一步的慢指针和一个每次走两步的快指针，如果链表里有环的话，两个指针最终肯定会相遇。
• 这个题蛋疼的是边界条件判定！！！先把边界case列出来！
• 时间时间复杂度均为O(n)，空间复杂度为O(1)。
• Beat34%

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        now1 = head
        now2 = head
        
        
        while(True):
            if(now1 == None or now2.next == None):
                return False
            if(now1.next != None and now2.next.next != None):  # 这里！先移动指针，再判断是否相遇
                now1 = now1.next
                now2 = now2.next.next
            else:
                return False
            
            if(now1 == now2):
                return True

参考答案

• https://leetcode.com/problems/linked-list-cycle/solution/