141. Linked List Cycle

Linked List Cycle

Problem Description

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

Approach 1) Brute-force

• The brute-force solution uses a Set. 
• We traverse through the entire list starting from the head of the list and add every new node encountered into the list.
• In case we come into a node that has already been encountered in the list then we return false. On reaching the last node if all nodes of the list are unique true is returned.
  
  

Let`s Code IT!

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let nodesSeen = new Set();
    while (head != null) {
        if (nodesSeen.has(head)) {
            return head;
        } else {
            nodesSeen.add(head);
        }
        head = head.next;
    }
    return null;
};

Approach 2) Two Pointer

Idea

For this problem, let's see what will happen if there's a circle.
If it's a little abstract, then let's think about we are running on a circular track.

If the track is 100m long, your speed is 10m/s, and your friend's speed is 5m/s. Then after your 20s, you've run 200m, and your friend has run 100m. But because the track is circular, so you will be at the same place as your friend since the difference between your distances is exactly 100m.

How about we change another track, change the speed of you and your friend? As long as your speeds are not the same, the faster person will always catch up with the slower person again.

That's the key point for this problem.

Solution

We just need to follow the strategy above - make a slower pointer and a faster pointer. Then we loop and loop again:

• if the fast pointer catches up with the slow pointer, then it's a circular linked list
• if the fast pointer gets to the end, then it's not a circular linked list

Let`s Code IT!

const hasCycle = (head) => {
  let fast = head;
  while (fast && fast.next) {
    head = head.next;
    fast = fast.next.next;
    if (head === fast) return true;
  }
  return false;
};

Complexity 

The time complexities of both methods remain the same that is O(n).
However, the space complexities of the two solutions vary the brute force solution will be O(n), and the optimal solution returns a space complexity of O(1) which is the space consumed by the list itself.

Conclusion

That’s all folks! In this post, we solved LeetCode problem #141. Linked List Cycle

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!