[LeetCode] Challenge log 141

Posted on | Edited on |

141. Linked List Cycle

Classic application of two pointers: slow and fast.

Algorithm: when fast catches up with slow, there is cycle.

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head: return False
    
        slow = head
        fast = head
        
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow: return True
            
        return False
0%