Linked List Cycle
Total Accepted: 74414 Total Submissions: 204066 Difficulty: Medium
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
https://leetcode.com/problems/linked-list-cycle/
Naive: O(N) space, O(N) time
# 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 """ if not head or not head.next: return False dic = {id(head): True} while head.next is not None: head = head.next if dic.get(id(head), None): return True else: dic[id(head)] = True return False
Use two pointers (one fast, one slow). The distance between them will increase from 0 to at most half of the length of the list, as the slow point traverses the linked list one node by one node. If there is a loop, the fast pointer will eventually meet with the slow pointer.
# 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 """ if not head or not head.next: return False slow_p = fast_p = head while fast_p and fast_p.next: slow_p, fast_p = slow_p.next, fast_p.next.next if slow_p is fast_p: return True return False