본문 바로가기
JAVA/Coding Test Study

[Easy] LeetCode - no.141 Linked List Cycle : Java

by ♡˖GYURI˖♡ 2024. 10. 21.
728x90

https://leetcode.com/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-interview-150

 

 

문제

주어진 LinkedList에 사이클이 존재하는지 여부를 판단할 것

 

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).

 

 

 

(이 때, 파라미터로는 시작 노드만 주어짐)

 

 

 

풀이1

    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();

        ListNode node = head;
        while (node != null && !set.contains(node)) {
            set.add(node);
            node = node.next;
        }

        return node != null;
    }

 

참고

 

LeetCode 141. Linked List Cycle

ListNode로 구현된 singly-linked list에서 사이클의 존재여부를 구하는 문제이다.문제를 보자마자 가장 쉽게 떠오르는 아이디어는 방문을 활용한 풀이이다. 노드를 next로 옮기면서 노드가 이미 방문한

velog.io

 

  • HashSet 사용
  • 노드를 통째로 Set에 add()
  • 만약 똑같은 노드가 나온다면 중간에 멈출 것
    • 이 때 현재 노드가 null이 아니라면 중간에 멈춘 것으로 판단
  • 현재 노드가 null이라면 끝까지 순회한 것이니 true, 아니면 false 반환
  • 시간복잡도 : O(N)

 

 

풀이2

    public boolean hasCycle2(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                break;
            }
        }

        if (fast == null || fast.next == null) {
            return false;
        }

        return true;
    }

 

참고

 

[리트코드] 141. Linked List Cycle / Javascript

문제주소 :https://leetcode.com/problems/linked-list-cycle/ Linked List Cycle - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 더보기

dev-note-97.tistory.com

 

 

  • 토끼와 거북이 알고리즘
    • 거북이는 한 칸씩, 토끼는 두 칸씩 이동
    • 순환구조가 있다면 토끼와 거북이가 언젠가 만나게 될 것이니 이를 통해 순환 여부를 판단
  • 토끼는 두 칸씩 이동해야 하니 fast와 fast.next 둘 다 null이 아닐 경우에만 이동 가능
  • slow와 fast가 일치할 경우 (똑같은 노드를 가리킬 경우) break
  • 만약 fast가 null이거나 fast.next가 null일 경우 (토끼가 리스트에 끝에 도달할 경우 = 순환X) false 반환, 아니라면 true 반환
  • 시간복잡도 : O(N)

💬 공간복잡도 면에서 효율적인 풀이