Linked List Cycle Program (Leetcode)

Linked List Cycle Program (Leetcode):

The Linked List Cycle program is a classic problem in computer science, often encountered in technical interviews and coding challenges. The task involves detecting whether a linked list contains a cycle, where a cycle occurs if any node in the list points back to a previous node, creating a loop. The challenge lies in efficiently determining whether such a cycle exists within the linked list. The typical approach involves using two pointers, known as the slow and fast pointers, to traverse the list. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. If there is a cycle, the fast pointer will eventually catch up to the slow pointer. By detecting this collision, the program can conclude that a cycle exists. Implementing this algorithm effectively requires careful consideration of edge cases and pointer manipulation to ensure accuracy and efficiency.

Given head, the head of a linked list, determines if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that the tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

 

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked list.

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Want to check about the Latest Electronic Devices: CompareKarein

# Definition for singly-linked list.

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

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        first = head
        second = head
        
        while first != None and second != None:
            if first.next == None or second.next == None:
                return False
            
            first = first.next
            second = second.next.next
            
            if first == second:
                return True
            
        return False