[LeetCode][Grind 75] 141. Linked List Cycle

해결 방안

순환이라면 결국 끝을 만나지 않고 계속 돌게 됩니다.

학교 운동장에서의 달리기를 생각하면 이해하기가 쉽습니다.

 

달리기가 빠른 철수와 조금 느린 짱구가 있다고 생각해보세요.

만약 달리기 코스가 운동장처럼 순환이 되는 원형이면 같은 시작점에서 출발해도 언젠가 철수와 짱구가 한번은 만나게 되겠죠(철수가 짱구를 따라잡는 순간)

하지만 달리기 코스가 순환이 되는 원형이 아니라 A부터 B지점까지 가는 직선 코스라면 이 2명은 철수가 끝지점에 도달할 때까지 한번도 만나지 않게 될 것입니다.

 

이 철수와 짱구를 각각 하나의 포인터라고 생각하고 투 포인터를 적용해서 문제를 풀어낼 수 있습니다.

 

1. `slow`와 `fast`라는 포인터를 생성합니다.
2. `slow`는 한 번에 한 노드씩 이동하고, `fast`는 한 번에 두 노드씩 이동합니다.
3. 순환이 된다면, 결국 `slow`와 `fast` 포인터가 만나게 됩니다.
4. 순환이 없다면, 만나지 않고 `fast` 포인터가 끝에 도달하게 됩니다.

겪은 문제점

처음에는 각 노드의 val이 중복이 없다고 생각하고, 리스트안에서 해당 값이 있는지 없는지 판단하는 방법으로 풀려고 했습니다. 하지만 이것은 문제 자체를 제대로 이해하지 못한 접근법이었습니다.

역시나 문제를 제대로 이해하는게 코딩 테스트에서 가장 중요합니다.

정답 코드

/**
 * 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) {
        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null){	//fast나 fast.next가 null이면 끝에 도달했다는 의미
            slow = slow.next;	// slow는 한 칸 이동
            fast = fast.next.next;	// fast는 두 칸 이동

            if(slow == fast){	// 두 포인터가 만나면 순환 링크드 리스트
                return true;
            }
        }

        return false;

    }
}