LeetCode: Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?

---

We can set up two pointers, a slow one and a fast one, the slow one move one step forward each time and the fast move two steps forward each time. If there exists a cycle, the slow one and fast will meet each other some time.

C++ Code:

/*
 * func: has_cycle
 * goal: to determine if there is a cycle in the linked list
 * @param head: head node
 * return: true or false
 */
bool has_cycle(ListNode *head){
    if(head == nullptr || head->next == nullptr){
        return false;
    }
    ListNode *slow = head;
    ListNode *fast = head;
    while(slow != nullptr && fast != nullptr && fast->next != nullptr){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
            return true;
        }
    }
    return false;
}

Python Code:

# func: to check if there is a cycle in the linked list
# @param head: head node of the list
# @return: True or False
def has_cycle(head):
    if not head or not head.next:
        return False
    slow = head
    fast = head
    while slow and fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False