Linked List

Floyd’s Tortoise and Hare

class FloydTortoiseAndHare

Implementation of Floyd’s Tortoise and Hare Algorithm

check_cycle(head)

Return True if cycle is present else False :param head: :return:

cycle_node(head)

Finding the node where cycle exists :param head: :return:

class FormLinkedList(array, ind)

Class to form linked-list with cycle

createll()

Function to create linked-list with cycle :return:

class Node(data=0, next=None)

Node for the linked-list

Description

Floyd’s cycle-finding algorithm is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. It is also called the tortoise and the hare algorithm

Checking the existence of the cycle in the linked-list. We can also find the node with which linked-list is linked

Important

• Linear TIme

• Constant Space

See also

Reference : wiki

Python

Check For Cycle

def check_cycle(self, head):
    """
    Return True is cycle is present else False
    :param head:
    :return:
    """
    # Two pointers
    tortoise, hare = head, head

    # Base Case
    while hare and hare.next:
        tortoise = tortoise.next
        hare = hare.next.next

        # Condition for cycle
        if tortoise == hare:
            return True

    # Condition when there is no cycle
    return False

Get the Node where cycle exists

def cycle_node(self, head):
    """
    Finding the node where cycle exists
    :param head:
    :return:
    """
    # Two pointers
    tortoise, hare = head, head

    while True:
        # Condition when pointer reaches to end
        if not hare or not hare.next:
            return None

        tortoise = tortoise.next
        hare = hare.next.next

        if tortoise == hare:
            break

    # Iterating over the ll to find
    tortoise = head
    while tortoise != hare:
        tortoise = tortoise.next
        hare = hare.next

    # Returning node where cycle was found
    return tortoise

Implementation

LeetCode

Sl No	Level	Questions	Solutions	Tags
141	Easy	Linked List Cycle	Python	Two Pointers
142	Medium	Linked List Cycle II	Python	Hash-Table, Two Pointers