卖萌的弱渣

I am stupid, I am hungry.

Linked List Cycle

Linked List Cycle

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

Example

Given -21->10->4->5, tail connects to node index 1, return true

Challenge

Can you solve it without using extra space?

Solution

  • Time: O(n)
  • Fast_node (step twice) and slow_node (step once), if two nodes meet, there is cycle.
(Linked-List-Cycle.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param head: The first node of the linked list.
    @return: True if it has a cycle, or false
    """
    def hasCycle(self, head):
        # write your code here
        if head == None or head.next == None:
            return False

        fast_node = head
        slow_node = head

        while fast_node != None and fast_node.next != None:
            fast_node = fast_node.next.next
            slow_node = slow_node.next
            if fast_node == slow_node:
                return True
        return False