[LeetCode] #141 Linked List Cycle (repeat:1)

이번 문제는 LinkedList에 사이클(Cycle)이 있는지 판단하는 문제이며, 미국 신입개발자들 인터뷰에 많이 나온 문제라고 한다. 이번 문제도 slow와 fast 포인터를 이용하여 쉽게 풀 수 있었다. 

 

# Description 

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.

 

 

 

 

# Solution 

public class Solution{
	public boolean hasCycle(ListNode head){
    	ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null){
        	slow = slow.next;
            fast = fast.next.next;
            
            if(slow == fast){
            	return true;
            }
        }
        
        return false;
    }
}

 

# Explanation

This method traverses LinkedList using two pointers , slow and fast. They both are initialized with head of the LinkedList. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. By the time when slow and fast points to the same node. It means there is a cycle in the LinkedList .Thefore returns true.

 

# Example of Nodes 

Suppose there is a cycle in the Node3

 

Initially

slow = Node1, fast = Node1

First, Initialize two pointers to the head of the LinkedList

 

Second Iteration 

slow = Node2 , fast = Node3

slow moves one node at a time, therefore points to the Node2. and fast moves two nodes at a time, therefore points to the Node3

 

Third Iteration 

slow = Node3, fast = Node3 

Here, I have to consider the cycle. since Node3 points to the Node2. fast reverses back to Node2 again and moves to the Node3 since fast moves two nodes at a time while slow reaches to the Node3. Thefore if slow meets fast, there is a cycle in the LinkedList

 

# Result 

Time Complexity : O(n) 

- two pointers iterates through the linkedlist using a while loop. The n represents the number of nodes in the list

Space Complexity : O(1) 

- the code uses only constant number of variables ('slow' and 'fast' pointers). and does not require additional memory propertional to the size of the input.

 

#  Interview Question  

-> In the while condition, fast != null and fast.next != null are both necessary to ensure that the code doesn't throw a NullPointerException 

fast != null : This condition checks if the fast pointer has reached the end of the Linked List. 

fast.next != null : Since the fast pointer moves two nodes at a time, this condition checks if there is at least one more node after the current fast node. If this condition was not existed. Then fast.next.next would result in a NullPointerException