Practice/Salesforce/Leetcode 142. Linked List Cycle II

Leetcode 142. Linked List Cycle II

CodingOptional

Problem

Given the head of a singly linked list, determine if the list contains a cycle. If a cycle exists, return the node where the cycle begins. If there is no cycle, return null.

A cycle occurs when a node's next pointer points back to a previous node in the list, creating a loop. The cycle does not necessarily start at the beginning of the list.

Requirements

1. Identify whether a cycle exists in the linked list
2. If a cycle exists, return the exact node where the cycle begins
3. If no cycle exists, return null
4. Do not modify the linked list structure
5. The solution should handle lists of any size, including single-node lists

Constraints

• The number of nodes in the list is in the range [0, 10^4]
• -10^5 ≤= Node.val ≤= 10^5
• pos indicates the index of the node that the tail connects to (0-indexed), or -1 if there is no cycle
• You cannot use extra space proportional to the input size (O(1) space complexity required)
• Time complexity should be O(n) where n is the number of nodes

Examples

Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: Node with value 2 Explanation: The tail of the list connects back to the node at index 1, which has value 2. This is where the cycle begins.

Example 2:

Input: head = [1,2], pos = 0 Output: Node with value 1 Explanation: The tail connects back to the first node, creating a cycle at the head of the list.

Example 3:

Input: head = [1], pos = -1 Output: null Explanation: There is no cycle in this single-node list.