Linked List Cycle - Python Solution

1. Introduction

The "Linked List Cycle" problem is a classic example of a fast and slow pointer technique in linked lists. It tests one's understanding of linked list traversal and cycle detection. The challenge is to identify whether a linked list has a cycle - a situation where a node's next pointer points to a previous node in the list, thus creating a loop.

Problem

Given the head of a linked list, the task is to determine if the linked list contains a cycle. A cycle occurs in a linked list when a node's next pointer points to an earlier node in the list. The goal is to return true if there is a cycle in the linked list, otherwise return false.

2. Solution Steps

1. Initialize two pointers, slow and fast, both pointing to the head of the list.

2. Traverse the linked list with these pointers - slow moves one step at a time, while fast moves two steps.

3. If at any point slow and fast meet, it indicates a cycle in the list.

4. If fast reaches the end of the list (i.e., fast or fast.next is null), there is no cycle.

5. Return true if a cycle is detected, otherwise false.

3. Code Program

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head):
    slow, fast = head, head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

# Example Usage
# Creating a list with a cycle for demonstration
node1 = ListNode(3)
node2 = ListNode(2)
node3 = ListNode(0)
node4 = ListNode(-4, node2)  # Creating a cycle
node1.next = node2
node2.next = node3
node3.next = node4
print(hasCycle(node1))  # Output: True

# List without a cycle
node1 = ListNode(1)
node2 = ListNode(2)
node1.next = node2
print(hasCycle(node1))  # Output: False

Output:

True
False

Explanation:

1. ListNode Class: ListNode class is used to represent each node in the linked list.

2. Fast and Slow Pointers: Two pointers, slow and fast, are used to traverse the list at different speeds.

3. Cycle Detection: If slow and fast meet, it indicates the presence of a cycle.

4. Traversal Logic: The fast pointer moves two steps for every one step of the slow pointer.

5. End Condition: If fast reaches the end of the list without meeting slow, there is no cycle.

6. Result: The function returns true if a cycle is detected, otherwise false.

7. Efficient Approach: This method efficiently detects a cycle without extra space or modifying the list.