Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/description/

Linked List Cycle - LeetCode

 

LinkedList 가 사이클을 이루며 이어져 있는지 체크하는 문제이다.
중복 체크를 위해선 가장 편한 방법 중 하나인 Set을 사용해주었다.
난이도는 특별히 높지 않았다.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;  
  
public class Solution {  
    public boolean hasCycle(ListNode head) {  
        Set<ListNode> set = new HashSet<>();  
        while(head != null){  
            if(set.contains(head)){  
                return true;  
            }  
            set.add(head);  
            head = head.next;  
        }  
  
        return false;  
    }   
}

 

다른 사람의 솔루션으로 속도가 좋은 방식으로는 아래와 같은 방식이 있었다. 별도의 자료구조를 사용하지 않고 두 개의 참조 값을 변화하며 비교만 하기에 속도가 뛰어났고 아이디어가 좋아 보였다.

public class Solution {
    public boolean hasCycle(ListNode head) {
        
        if(head==null||head.next==null){
            return false;
        }
        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;
    }
}