[leetcode] Linked List Cycle

Problem

what to ask?

Is it a node?
Is it a array?
what is pos? Is it a index where Node start repeating?
Extreme case? head = null?
constraints?
where does this come from?

Code

sol 1 - using an address of a node

/**
 * 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 == null || head.next == null) return false;
        
        Set<ListNode> set = new HashSet<>();
        for (;;)
        {
            if (head.next == null)
                return false;
            if (set.contains(head))
                return true;
            set.add(head);
            head = head.next;
        }
    }
}

time O(N)
space O(N)

sol 2 - two pointer solution

slow moves 1 step each
fast moves 2 step each
If there is a cycle, there exists slow == fast is true!

then why its time complexity is constant time? with n elements?

• m, steps that take, must be less than n

ex)
[3, 2, 0, -4, 5], pos=1 => [1, 2, 3, 4, 1]
slow 2 3 4 1 2 3 4 1
fast 3 1 3 1

public class Solution {
    public boolean hasCycle(ListNode head) {
		if (head == null || head.next == null) return false;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null || fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        
        return false;
    }
}

time O(1)
space O(1)

sol 3 - extra: clever! using constraints limit

public class Solution {
    public boolean hasCycle(ListNode head) {
		int len = 10000;
		
        if (head == null) return false;
        
		int i = 0;
        while (i < len)
        {
        	head = head.next;
        	if (head.next == null) return false;
            
        }
        
        return true;
        
    }
}