Linked list Has Loop

 

Linked List with a Loop: A linked list with a loop (or a circular linked list) is a type of linked list where the last node of the list points back to one of the previous nodes, creating a loop or cycle in the list structure.

To represent a linked list with a loop, we use the ListNode class, which consists of a value and a next pointer. The next pointer points to the next node in the list. In the case of a circular linked list, the next pointer of the last node points back to one of the previous nodes in the list, creating a loop.

Solving LeetCode Problem - "Linked List Cycle": The problem we'll solve is called "Linked List Cycle," where we need to determine if a given linked list contains a cycle.

Here's the complete code with detailed comments:


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


def has_cycle(head):
    """
    Checks if the given linked list contains a cycle.
    """
    if not head or not head.next:
        return False

    slow = head
    fast = head.next

    while slow != fast:
        if not fast or not fast.next:
            return False

        slow = slow.next
        fast = fast.next.next

    return True


# Example usage
# Create a linked list with a cycle
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node2  # Creating a cycle

# Check if the linked list contains a cycle
has_cycle_result = has_cycle(head)
print("Linked List Contains Cycle:", has_cycle_result)  # Output: True

Explanation:

  1. We define the ListNode class to represent a node in the linked list. Each node has a value and a next pointer that points to the next node in the list.
  2. The has_cycle function takes the head of the linked list as input and checks if the list contains a cycle. If there is a cycle, it returns True; otherwise, it returns False.
  3. In the has_cycle function, we use the slow and fast pointer approach to detect a cycle. We initialize two pointers, slow and fast, both pointing to the head node.
  4. We iterate through the linked list with the slow and fast pointers. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.
  5. If there is a cycle in the linked list, the fast pointer will eventually catch up with the slow pointer. In this case, we return True.
  6. If there is no cycle and the fast pointer reaches the end of the linked list (i.e., it becomes None or the next pointer of the fast pointer becomes None), we return False.

Time and Space Complexity Analysis:

  • The time complexity of detecting a cycle in a linked list using the slow and fast pointer approach is O(n), where n is the number of nodes in the linked list. We traverse the linked list once.
  • The space complexity is O(1) because we only use two pointers, slow and fast, to detect the cycle. We don't use any additional data structures that scale with the input size.

The problem we'll solve is called "Linked List Cycle II" from LeetCode. Given a linked list, we need to return the node where the cycle begins if there is a cycle, or return null if there is no cycle.

Here's the complete code with detailed comments:


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


def detect_cycle(head):
    """
    Returns the node where the cycle begins in the linked list,
    or None if there is no cycle.
    """
    if not head or not head.next:
        return None

    # Step 1: Check if a cycle exists
    slow = head
    fast = head

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

        if slow == fast:
            break
    else:
        # No cycle found
        return None

    # Step 2: Find the node where the cycle begins
    slow = head

    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow


# Example usage
# Create a linked list with a cycle
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node3  # Creating a cycle

# Find the node where the cycle begins
cycle_node = detect_cycle(head)
if cycle_node:
    print("Cycle Begins at Node with Value:", cycle_node.val)  # Output: 3
else:
    print("No Cycle Found")

Explanation:

  1. We define the ListNode class to represent a node in the linked list. Each node has a value and a next pointer that points to the next node in the list.
  2. The detect_cycle function takes the head of the linked list as input and returns the node where the cycle begins, or None if there is no cycle.
  3. In the detect_cycle function, we use the slow and fast pointer approach to detect a cycle. We initialize two pointers, slow and fast, both pointing to the head node.
  4. We iterate through the linked list with the slow and fast pointers. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.
  5. If there is a cycle in the linked list, the fast pointer will eventually catch up with the slow pointer. This indicates the presence of a cycle.
  6. After detecting the cycle, we reset the slow pointer to the head node and move both the slow and fast pointers one step at a time. The point at which they meet again is the node where the cycle begins.
  7. Finally, we return the node where the cycle begins or None if no cycle is found.

Time and Space Complexity Analysis:

  • The time complexity of detecting the cycle and finding the node where the cycle begins is O(n), where n is the number of nodes in the linked list. We traverse the linked list at most twice.
  • The space complexity is O(1) because we only use two pointers, slow and fast, to detect the cycle and find the cycle's starting node. We don't use any additional data structures that scale with the input size.

 

 

 

Next Post Previous Post