0141 - Linked List Cycle (Easy)

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).

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.

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

/**
 * 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) {
        ListNode slowPointer = head;
        ListNode quickPointer = head;

        if(head == null) return false;

        while(head != null) {
            // slow pointer, move one step each time.
            slowPointer = slowPointer.next;
            if(slowPointer == null) return false;

            // quick pointer, move two steps each time.
            quickPointer = quickPointer?.next?.next;
            if(quickPointer == null) return false;

            // slow pointer meets quick pointer means that there is a cycle in this linked list
            if(slowPointer == quickPointer) return true;
        }

        return false;
    }
}

# 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:
        slowPointer = head
        quickPointer = head

        if head == None:
            return False

        while head != None:
            # slow pointer, move one step each time.
            slowPointer = slowPointer.next
            if slowPointer == None:
                return False

            # quick pointer, move two steps each time.
            quickPointer = quickPointer.next.next if quickPointer.next != None else None
            if quickPointer == None:
                return False

            # slow pointer meets quick pointer means that there is a cycle in this linked list
            if slowPointer == quickPointer:
                return True

        return False

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
// Time complexity: O(n), where n - # of nodes in the list
// Space complexity: O(1)
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        // Fast & Slow pointer
        ListNode slow = head;
        ListNode fast = head;
        // Fast Reference to check if it's not null, because it's traverse twice as fast as slow
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // If both meet at the same node then there is a loop
            if (slow == fast) {
                return true;
            }
        }
        // If no loop, fast pointer at the end reached it's last node null pointer
        return false;
    }
}

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next;
    if (slow == fast) {
      return true;
    }
  }
  return false;
};

/**
 * 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) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
};