[leetcode - Java] 141. Linked List Cycle

먼저 이번 문제의경우 문제를 보고도 이해하지 못했고 접근 방식도 전혀 몰랐기에 코드에대한 분석 or 리뷰 정도가 될 것 같다.

1. 문제

---

- Linked List가 주어지면 목록에 순환이 포함되어 있는지 확인하는 문제

2. 정답 코드

---

// 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) {

    }
}

문제를 들어오면 가장 윗부분에 주석된 코드가 있을 것이다. 아마도 Linked List의 흐름에 대해 정의해둔 것을 알려주는 코드로 판단되며 참고해서 Solution 클래스를 작성하면 될 것 같았다. 완성된 코드와 실행 결과는 아래와 같다.

// 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) {
        System.out.println("1 head = " + head);
        System.out.println("1 head.val = " + head.val);
        System.out.println("1 head.next = " + head.next);

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

        ListNode slow = head;
        ListNode fast = head.next;
        System.out.println("1 slow = " + slow);
        System.out.println("1 fast = " + fast);

        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
            System.out.println("2 slow = " + slow);
            System.out.println("2 fast = " + fast);
        }
        return true;
    }
}

1 head.val = [3,2,0,-4]에서 첫 번째 데이터인 3
1 head = 3의 주소값
1 head.next = 3의 다음 데이터인 2의 주소값
1 slow = 1 head = 3의 주소값 (한 번에 한 노드 이동)
1 fast = 1 head.next = 3의 다음 데이터인 2의 주소값 (한 번에 두 노드 이동)
2 slow = 1 slow 다음 주소값 = 1 fast
2 fast = 1 fast 다음 주소값
위 과정을 반복 실행하여 slow와 fast가 겹치는 주소값을 찾는다.