Circular Linked List

 A circular linked list is a variation of the linked list where the last node's next reference points back to the first node, forming a loop. This allows for circular traversal and is useful in certain scenarios.

In Python, we can implement a circular linked list by creating a Node class and a CircularLinkedList class that manages the nodes.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def insert(self, value):
        # Create a new node with the given value
        new_node = Node(value)
        
        # If the linked list is empty, set the new node as the head
        if self.head is None:
            self.head = new_node
            self.head.next = self.head
        else:
            # Traverse to the end of the list and append the new node
            curr = self.head
            while curr.next != self.head:
                curr = curr.next
            curr.next = new_node
            new_node.next = self.head

    def delete(self, value):
        if self.head is None:
            return
        
        # If the head node has the value, update the head to the next node
        if self.head.value == value:
            curr = self.head
            while curr.next != self.head:
                curr = curr.next
            curr.next = self.head.next
            self.head = self.head.next
            return

        # Traverse the linked list to find the node with the given value
        curr = self.head
        prev = None
        while curr.next != self.head:
            if curr.value == value:
                # Remove the node by updating the previous node's next reference
                prev.next = curr.next
                return
            prev = curr
            curr = curr.next
        
        # Check if the last node has the value
        if curr.value == value:
            prev.next = self.head

    def search(self, value):
        # Traverse the circular linked list to find the node with the given value
        curr = self.head
        while True:
            if curr.value == value:
                return True
            curr = curr.next
            if curr == self.head:
                break
        return False

Now let's solve a question from LeetCode using the Circular Linked List. Consider the problem "Linked List Cycle" (LeetCode #141), where we need to determine if a linked list has a cycle. 

def has_cycle(head):
    slow = head
    fast = head

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

        if slow == fast:
            return True

    return False

In this example, we use the "Floyd's Tortoise and Hare" algorithm to detect a cycle in the linked list. We initialize two pointers, slow and fast, both starting from the head. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle, the fast pointer will eventually catch up to the slow pointer. If the fast pointer reaches the end of the list (i.e., it becomes None), then there is no cycle. We return True if a cycle is detected and False otherwise.

The time complexity of the has_cycle function is O(N), where N is the number of nodes in the linked list. In the worst case, the fast pointer will travel the entire linked list before determining the absence of a cycle.

Here's another example of solving a LeetCode problem using the Circular Linked List concept. Let's consider the problem "Find the Duplicate Number" (LeetCode #287).

Problem statement: Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one duplicate number in nums, return this duplicate number.

Example: Input: nums = [1,3,4,2,2] Output: 2

To solve this problem, we can utilize the concept of the Floyd's Tortoise and Hare algorithm to find the duplicate number.

def find_duplicate(nums):
    slow = nums[0]
    fast = nums[0]

    # Move slow and fast pointers
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]

        if slow == fast:
            break

    # Find the entrance of the cycle
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

In this example, we initialize two pointers, slow and fast, to the first element of the nums array. We update the slow pointer by accessing the value at the corresponding index in nums, and the fast pointer by accessing the value at the index of the value at the corresponding index in nums. We repeat this process until the pointers meet at the same value. This indicates the presence of a cycle.

Once we detect the cycle, we reset the slow pointer to the first element of the nums array and move both the slow and fast pointers one step at a time. The point at which they meet again is the entrance of the cycle. In the context of the problem, this entrance represents the duplicate number.

The time complexity of the find_duplicate function is O(n), where n is the length of the nums array. The space complexity is O(1), as we are using constant extra space for the pointers.