LeetCode 141(Linked List Cycle, java)

0. 문제

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

Linked List Cycle - LeetCode

 

1. 문제 설명

- 문제에서 한 개의 연결 리스트(head)가 주어진다.

- 연결 리스트를 탐색하여 순환이 존재하는지 판단하는 것이 문제의 핵심이다. 

 

2. 문제 해설

- 이 문제는 자칫 어려워 보일 수 있다.

- 다만, 문제의 제약조건을 힌트로 사용한다면 굉장히 쉽게 풀리는 문제이다.

- 알고리즘을 풀다 보면 문제를 잘 읽지 않아서 못 푸는 경우가 허다하다.

- 단순히 문제를 읽고 이해할 뿐만 아니라, 주어진 제약조건 또한 힌트가 된다는 것을 인지하자. 

 

a) 첫 번째 접근

- 가장 아래의 제약조건을 살펴보자.

- Node.val이 최대 10^5 까지 될 수 있다고 나와있다.

- 자바는 최대 -21억 ~ 21억까지 표현할 수 있다. 

- 10^5는 10만이다. 그러므로 충분히 int형으로 표현 가능한 범위라는 것을 인지해야 한다. 

 

b) 두 번째 접근 

- 이제 순환을 판단하는 방법에 대해서 이야기해보자.

 

- 첫 번째 접근에 왜 int의 표현 범위에 대해서 언급했을까? 

- 이것과 순환을 찾는 것이 무슨 연관 관계가 있을까?

 

- 이번 문제는 연결 리스트의 순환을 판단하기가 상당히 까다롭다.

- 어떤 노드를 시작으로 순환이 발생하는지 알 수 없기 때문이다. 

 

- 문제의 예시에서는 어떤 노드가 순환 노드인지를 알려주지만, 이는 매개변수로 주어지지 않는다.

- 그러므로 문제를 푸는 사람의 입장에서는 어떤 노드가 순환의 시작인지 알 수 없다. 

 

- 그렇다면 순환을 어떻게 정의할 수 있을까?  

 

- 만약 3개의 노드(1, 2, 3)가 순환한다고 해보자. (문제를 푸는 사람은 이를 알지 못한다.)

- N번째부터 N + 2번째까지 어떤 3개의 숫자가 반복되었다고 해보자.

   ex) 1 → 2 → 3 → 1(N) → 2(N + 1) → 3(N + 2)

 

- 이런 경우, 순환이 존재한다고 할 수 있을까?

- 아니다. N + 2번째 이후 숫자도 계속해서 반복하는지를 알아야 하기 때문이다.

   ex)   1 → 2 → 3 → 1 → 2 → 3 → 5 → 6 → 1 → 4 → 3 

 

- 만약 계속해서 반복하는 숫자가 등장한다면 순환이라고 판단할 수 있을까?

- 아니다. 순환이라면 동일한 노드를 사용해야 한다.

- 즉, 동일한 메모리 주소를 가진 객체가 반복하여 등장해야 한다. 

 

- 이 과정을 계속해서 반복하다 보면, 결국 순환의 시작을 알지 못하면 순환을 파악할 수 없다는 결론에 이른다. 

- 그러므로 문제의 제약조건에 언급된 표현 가능한 수의 범위를 이용한다. 이를 일종의 flag로 사용하는 것이다. 

 

- 다음 코드를 보면서 이해해보자. 

 

3. 정답 코드

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

 

- 위의 코드에서 모든 노드의 값을 9999999로 재설정한다.

- 9999999는 10^5를 초과하는 수로, 노드가 가질 수 없는 숫자다.