[LeetCode - 141] Linked List Cycle - Java

문제 설명

문제

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.

 

입출력 예시

 

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

 

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.

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

 

제한사항

• The number of the 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.

 

풀이 : Success

소스 코드

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        int pos = 1;
        ListNode curr = head;
        while(curr.next != null){

            if(checkAddress(head, curr.next, pos)){
                return true;
            }
            curr = curr.next;
            pos++;
        }

        return false;
    }
    public boolean checkAddress(ListNode head, ListNode curr, int pos){

        for (int i = 0; i < pos; i++) {
            if(head == curr){
                return true;
            }
            head = head.next;
        }

        return false;
    }
}​

 

풀이 회고

우선 입력받는 연결리스트가 null인 경우 당연히 싸이클을 갖지 않으므로 false를 반환하도록 해주었다.

 

문제를 해결하기 위한 접근 방법으로는 연결리스트를 처음부터 끝까지 순회하면서 현재 노드가 가리키는 다음 노드가 현재 노드 이전에 있었던 노드를 가리키는지(=싸이클이 존재하는지)를 검사하도록 했다.

 

이를 위해 while(curr.next != null) 반복문을 통해 연결리스트를 순회하도록 했고 연결리스트 처음 node를 가리키는 head와 현재 node에서 다음 node를 가리키는 curr.next 그리고 직전까지의 node를 나타내기 위한 별도 변수 pos(1로 초기화)를 인자로 두어 checkAddress 메서드를 호출하였다.

 

이때 한번씩 순회할 때마다 가리키는 node 역시 다음 node로 이동하므로 pos를 1씩 증가시켜주도록 했다.

 

checkAddress 메서드에서 만일 현재 node가 가리키는 node가 이전에 있었던 node라면 true를 반환하도록 했고(싸이클이 존재) 그게 아니라면(for문 종료) false를 반환하도록 했다.

 

하지만 현재 문제에서는 노드의 개수가 최대 10000개이므로 이런 식으로 매번 순회할 때마다 이전 노드들을 검사하는 것은 매우 비효율적이다.

 

모범 소스코드

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

 

코드 분석

위 풀이는 리트코드 내 수많은 모범 답안 중 하나이다. 일단 나의 풀이 보다 훨씬 간결하다.

 

해당 풀이에서는 나와는 전혀 다른 접근 방법을 취했다. 연결리스트를 순회할 때 처음 node를 가리키는 ListNode형 변수 2개(fast, slow)를 선언해준 후 fast는 다음 다음 노드를 가리키도록, slow는 다음 노드를 가리키도록 했다. fast와 slow는 다음 노드를 가리키는 간격이 다르기 때문에 연결리스트를 계속 순회하다 보면 만나게 되고 이들이 만난다는 것은 결국 싸이클이 존재하다는 것과 같다.

 

만일 싸이클이 존재하지 않았으면 while 반복문 조건식 fast.next != null && fast.next.next != null에 의해 진작에 while 반복문이 종료 되고 false를 반환했을 것이다.

 

 

참고자료

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