Follow up:
Can you solve it without using extra space?
Solution:
Using a fast pointer that advances two nodes each time and a slow pointer that advances on node, we always detect a cycle as the fast pointer cannot overtake the slow one without being in the same node in one of the ``turns".# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @return a boolean
def hasCycle(self, head):
fastPointer = head
slowPointer = head
while fastPointer != None and fastPointer.next != None:
fastPointer = fastPointer.next.next
slowPointer = slowPointer.next
if fastPointer == slowPointer:
return True
return False
No comments :
Post a Comment