문제 // 자료구조 // 리스트(List) // 순환 // toJava

/**
 * [루프발견]
 *  순환 연결리스트가 주어졌을때, 순환되는 부분의 첫째노드를 반환하는 알고리즘을 작성
 *  순환 연결리스트란 노드의 next 포인터가 앞선 노드들 가운데 어느 하나를 가리키도록 설정되어 있는,
 *  엄밀히 말해서 변질된 방식의 연결리스트를 의미한다.
 *
 * [예제]
 *  A -> B -> C -> D -> E -> C [앞에 나온 C와 같음]
 *
 * [풀이]
 *  => 새로운 노드가 나올때마다 기존에 나왔던 노드인지 계속 확인을 해줘야 한다.
 *  => Buffer 방식 or Runner 방식
 *
 * */

public class Q08 {

    /* Node */
    static class Node {
        Node next;
        int data;
        Node(int data) {
            this.data = data;
        }
    }

    /* buffer방식 */
    public Node checkCircular(Node head) {
        List<Node> buffers = new ArrayList<>();
        Node current = head;
        while(current != null) {
            for(Node n : buffers) {
                if(n == current) return current;
            }
            buffers.add(current);
            current = current.next;
        }
        return null;
    }

    /* runnber방식 */
    public Node findBeginning(Node head) {
        Node slow = head;
        Node fast = head;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {
                break;
            }
        }

        // == 순환 아닐때==
        if(fast == null || fast.next == null) {
            return null;
        }

        // == 시작점 확인==
        slow = head;
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return fast;
    }
}