문제 // 자료구조 // 리스트(List) // 교집합 // toJava

/**
 * [교집합]
 *  단방향 연결리스트 두개가 주어졌을때 이 두 리스트의 교집합 노드를 찾은 뒤 반환하는 코드를 작성하라
 *  여기서 주소는 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다.
 *  즉 첫번째 리스트에 있는 k번째 노드와 두번째 리스트에 있는 j번쨰 노드가 주소까지 완전히 같다면 교집합 원소이다.
 *
 * [풀이]
 *  => 리스트의 노트간에 공유가 가능한가
 *  => 만약 주소가 같은 노드가 있다면 그 뒤로는 모두 같다.
 *      => 마지막 노드는 항상 같다.
 *
 * */

public class Q07 {

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

    /* Result */
    static class Result {
        public Node tail;
        public int size;
        public Result(Node tail, int size) {
            this.tail = tail;
            this.size = size;
        }
    }

    /* findIntersection */
    static Node findIntersection(Node listA, Node listB) {
        if(listA == null || listB == null) return null;

        Result resultA = getTailAndSize(listA);
        Result resultB = getTailAndSize(listB);

        Node shorter = resultA.size < resultB.size ? listA : listB;
        Node longer = resultA.size < resultB.size ? listB : listA;

        // == 길이맞추기 ==
        longer = getKthNode(longer, Math.abs(resultA.size - resultB.size));

        while(shorter != longer) {
            shorter = shorter.next;
            longer = longer.next;
        }

        return longer;
    }

    static Result getTailAndSize(Node list) {
        int size = 1;
        Node current = list;
        while (current.next != null) {
            size++;
            current = current.next;
        }
        return new Result(current, size);
    }

    static Node getKthNode(Node head, int k) {
        Node current = head;
        while(k > 0 && current != null) {
            current = current.next;
            k--;
        }
        return current;
    }


}