[LeetCode/Java] 141. Linked List Cycle

0. 문제

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

1. 문제 설명

• LinkedList의 head가 주어질 때, 해당 LinkedList가 사이클을 형성하는가?
• 사이클이란 연속해서 다음 포인터를 따라갈 때 LinkedList 내의 특정 원소로 다시 도달할 수 있다는 뜻이다.

2. 문제 풀이

2.1. 접근법

• 사이클이란 특정 원소로 돌아올 수 있다는 것을 말한다.
• 즉, 1 → 2 → 3 → 1 → 2 → 3은 사이클이 맞지만, 1 → 2 → 3 → 2 → 1 → 3은 사이클이 아니다.
• 문제의 제약 조건을 확인하면 val의 최대값은 100000이다.
• 따라서, LinkedList를 순회하면서 val 값을 100001(100000 + 1)로 바꾸면서, head.next가 100001이면 해당 리스트는 사이클을 형성했다고 할 수 있다.

3. 코드

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        while (head != null) {
            if (head.val == 100001) return true;
            head.val = 100001;
            head = head.next;
        }
        return false;
    }
}

4. 결과