linked_list_cycle

View Source

 1from utils import ListNode
 2from typing import Optional
 3
 4
 5# @leet start
 6class Solution:
 7    def hasCycle(self, head: Optional[ListNode]) -> bool:
 8        """
 9        To figure out if a linked list has a cycle, we can do the following:
10        We first know that linked lists that dont have a head and a pointer cannot
11        have cycles (since they have 0 or 1 elements), and cannot create a self-cycle.
12
13        We iterate the slow pointer by one and the fast pointer by two, and then
14        check if they intersect. If they don't intersect, there's no cycle.
15
16        If they do intersect, there is a cycle.
17        """
18        # A linked list without a next pointer can't have cycles
19        if not head or not head.next:
20            return False
21
22        slow = head
23        fast = head.next
24
25        while fast and fast.next:
26            if slow == fast:
27                return True
28            slow = slow.next
29            fast = fast.next.next
30
31        # this is unreachable
32        return False
33
34
35# @leet end
36def test():
37    assert 2 + 2 == 4

class Solution: View Source

 7class Solution:
 8    def hasCycle(self, head: Optional[ListNode]) -> bool:
 9        """
10        To figure out if a linked list has a cycle, we can do the following:
11        We first know that linked lists that dont have a head and a pointer cannot
12        have cycles (since they have 0 or 1 elements), and cannot create a self-cycle.
13
14        We iterate the slow pointer by one and the fast pointer by two, and then
15        check if they intersect. If they don't intersect, there's no cycle.
16
17        If they do intersect, there is a cycle.
18        """
19        # A linked list without a next pointer can't have cycles
20        if not head or not head.next:
21            return False
22
23        slow = head
24        fast = head.next
25
26        while fast and fast.next:
27            if slow == fast:
28                return True
29            slow = slow.next
30            fast = fast.next.next
31
32        # this is unreachable
33        return False

def hasCycle(self, head: Optional[utils.ListNode]) -> bool: View Source

 8    def hasCycle(self, head: Optional[ListNode]) -> bool:
 9        """
10        To figure out if a linked list has a cycle, we can do the following:
11        We first know that linked lists that dont have a head and a pointer cannot
12        have cycles (since they have 0 or 1 elements), and cannot create a self-cycle.
13
14        We iterate the slow pointer by one and the fast pointer by two, and then
15        check if they intersect. If they don't intersect, there's no cycle.
16
17        If they do intersect, there is a cycle.
18        """
19        # A linked list without a next pointer can't have cycles
20        if not head or not head.next:
21            return False
22
23        slow = head
24        fast = head.next
25
26        while fast and fast.next:
27            if slow == fast:
28                return True
29            slow = slow.next
30            fast = fast.next.next
31
32        # this is unreachable
33        return False

To figure out if a linked list has a cycle, we can do the following: We first know that linked lists that dont have a head and a pointer cannot have cycles (since they have 0 or 1 elements), and cannot create a self-cycle.

We iterate the slow pointer by one and the fast pointer by two, and then check if they intersect. If they don't intersect, there's no cycle.

If they do intersect, there is a cycle.

def test(): View Source

37def test():
38    assert 2 + 2 == 4