LeetCode-in-All

141. Linked List Cycle

Easy

Given head, the head of a linked list, determine 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 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?

Solution

import com_github_leetcode.ListNode;

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

Time Complexity (Big O Time):

• The program uses two pointers, fast and slow, to traverse the linked list.
• The fast pointer moves twice as fast as the slow pointer in each iteration.

The key insight here is that if there is a cycle in the linked list, the fast and slow pointers will eventually meet (i.e., fast == slow). If there is no cycle, the fast pointer will reach the end of the list (i.e., fast == null or fast.next == null) before the slow pointer.

Therefore, the time complexity of this algorithm is O(N), where N is the number of nodes in the linked list. This is because in the worst case, when there is no cycle, both pointers will traverse the entire linked list once.

Space Complexity (Big O Space):

The space complexity of this algorithm is O(1), which means it uses a constant amount of extra space regardless of the size of the input linked list. This is because it only uses two additional pointers (fast and slow) to traverse the list and does not rely on additional data structures or recursion that would consume additional memory.

In summary, the time complexity of this program is O(N), and the space complexity is O(1), where N is the number of nodes in the linked list.

This site is open source. Improve this page.