Solution For Linked List Cycle

The Linked List Cycle problem on LeetCode is a classic problem that involves identifying whether a linked list has a cycle or not. In this problem, you are given a linked list and are to determine whether it has a cycle or not.

A linked list consists of a series of nodes that are connected to each other. Each node contains a value and a reference to the next node in the list. If the last node in the list has a reference to null, then the linked list is considered to be terminated. However, if any node in the list references an earlier node, then the linked list contains a cycle.

To solve this problem, we need to use the Floyd’s cycle-finding algorithm, also known as the “turtle and hare” algorithm. This algorithm involves traversing the linked list with two pointers, one moving faster than the other. If the linked list contains a cycle, then the faster pointer will eventually catch up to the slower pointer, indicating that a cycle has been found.

Here’s the detailed solution:

1. We start by initializing two pointers, slow and fast, to point to the head of the linked list.
2. We then iterate through the linked list. During each iteration, the slow pointer moves one step forward while the fast pointer moves two steps forward.
3. We check at each step whether the fast pointer has reached the end of the list or not. If it has, then the linked list does not contain a cycle. Otherwise, we continue iterating through the list.
4. If the fast pointer catches up to the slow pointer, then a cycle has been found, and we return true. Otherwise, we return false.

Here’s the Python code that implements this approach:

“`
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head:
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

“`

In the code above, we first check whether the head of the linked list is None. If it is, then we know for sure that the linked list does not contain a cycle (since there are no nodes to iterate through).

We then initialize the slow and fast pointers to point to the head of the linked list and its next node, respectively. We then iterate through the linked list using a while loop. During each iteration, we check whether the fast pointer has reached the end of the list (i.e., it is pointing to None), in which case we know for sure that the list does not contain a cycle. Otherwise, we move the slow pointer one step forward and the fast pointer two steps forward.

Finally, if the fast pointer ever catches up to the slow pointer, then we know that a cycle has been found, and we return True. Otherwise, we return False.

This solution has a time complexity of O(n), where n is the number of nodes in the linked list. It also has a space complexity of O(1), since we are only using two pointers to traverse the linked list.

Step by Step Implementation For Linked List Cycle

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        // if head is null, there is no cycle
        if (head == null) {
            return false;
        }
        
        // if head.next is null, there is no cycle
        if (head.next == null) {
            return false;
        }
        
        // create two pointers, slow and fast
        // slow moves one node at a time
        // fast moves two nodes at a time
        ListNode slow = head;
        ListNode fast = head.next;
        
        // while fast is not null and fast.next is not null
        // keep iterating
        while (fast != null && fast.next != null) {
            // if slow == fast, there is a cycle
            if (slow == fast) {
                return true;
            }
            // move slow one node
            slow = slow.next;
            // move fast two nodes
            fast = fast.next.next;
        }
        
        // if we reach here, that means there is no cycle
        return false;
    }
}

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        # check for empty list
        if not head:
            return False
        
        # if only one element in list, can't be a cycle
        if not head.next:
            return False
        
        # use Floyd's cycle detection algorithm
        # two pointers, one moves one node at a time, 
        # the other moves two nodes at a time
        # if there is a cycle, the two pointers will eventually meet
        
        slow = head
        fast = head.next
        
        while slow != fast:
            # check for end of list - no cycle
            if not fast or not fast.next:
                return False
            
            slow = slow.next
            fast = fast.next.next
        
        return True

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    // if head is null, return false
    if (!head) {
        return false;
    }
    
    // define two pointers, slow and fast
    let slow = head;
    let fast = head;
    
    // while loop will continue until slow === fast (which means they met in the cycle)
    // or fast.next === null (which means there is no cycle)
    while (slow !== fast || fast.next !== null) {
        // if fast.next is null, that means there is no cycle
        if (fast.next === null) {
            return false;
        }
        
        // move slow pointer one node at a time
        slow = slow.next;
        
        // move fast pointer two nodes at a time
        fast = fast.next.next;
    }
    
    // if the while loop exits, that means there is a cycle
    return true;
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) return false;
        ListNode *slow = head, *fast = head->next;
        while (slow != fast) {
            if (!fast || !fast->next) return false;
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public bool HasCycle(ListNode head) {
        // if head is null or only has one node, then it can't have a cycle
        if (head == null || head.next == null) {
            return false;
        }
        
        // use two pointers, slow and fast
        // slow moves one node at a time, while fast moves two nodes at a time
        // if there is a cycle, slow and fast will eventually meet
        ListNode slow = head;
        ListNode fast = head.next;
        
        while (slow != fast) {
            // if fast reaches the end of the list, then there is no cycle
            if (fast == null || fast.next == null) {
                return false;
            }
            
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return true;
    }
}