Daily Leetcoding Challenge 141. Linked List Cycle

해커톤에 코딩테스트에 인터뷰 준비에 여러모로 바빠져서 며칠간 포스팅을 못했다. 9월 4일 오늘의 문제는 링크드 리스트에서 사이클을 찾는 문제였다.

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

Linked List Cycle - LeetCode

직관

오늘 풀어본 문제는 난이도가 Easy라서 꽤나 직관적인 문제가 나왔다. 링크드 리스트에서 사이클을 찾으려면 두 개의 포인터(slow, fast)를 사용하면 된다. slow는 한 번에 하나씩 노드를 순회하고, fast는 한 번에 두개씩 노드를 순회한다. 만약 사이클이 존재한다면 fast가 slow와 와 같은 노드를 바라보는 순간이 올 것이고, 그렇지 않다면 fast는 리스트 끝까지 가서 null이 될 것이다.

접근법

two pointers

 

복잡도

LinkedList의 길이를 n이라고 했을 때 시간 복잡도는 O(n), 공간 복잡도는 O(1)이다.

코드

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