// D. Scott
// CCI - Problem 2.7
// Determine whether two singly linked lists intersect

class Node {
    Node next = null;
    int data;
    
    public Node(int d) {
        data = d;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

public static void main (String[] args)
{
    // Generate lists
    Node list1 = new Node(5);
    Node head1 = list1;
    list1.appendToTail(3);
    list1.appendToTail(8);
    list1.appendToTail(6);
    list1.appendToTail(2);
    list1.appendToTail(16);
    list1.appendToTail(33);
    list1.appendToTail(1);
    
    Node list2 = new Node(12);
    Node head2 = list2;
    list2.appendToTail(16);
    list2.appendToTail(4);
    list2.appendToTail(5);
    list2.appendToTail(9);
    list2.appendToTail(6);
    list2.appendToTail(2);
    
    while (list1.data != 2) 
        list1 = list1.next;

    while (list2.next != null) 
        list2 = list2.next;

    
    list2.data = list1.data;
    list2.next = list1.next;

    list1 = head1;
    list2 = head2;
    
    System.out.println("List 1:");
    while (list1 != null) {
        System.out.print(list1.data + " ");
        list1 = list1.next;
    }
    System.out.println("\n\nList 2:");
    while (list2 != null) {
        System.out.print(list2.data + " ");
        list2 = list2.next;
    }
      
    list1 = head1;
    list2 = head2;
    
    boolean intersect = false;
    Node inters_node = new Node(0);
    int elem1 = 0;
    int elem2 = 0;
    // Compare lists for intersection node
    while (list1 != null && intersect == false) {
        list2 = head2;
        elem2 = 0;
        while (list2 != null && intersect == false) {
            if (list1.data == list2.data && list1.next == list2.next) {
                intersect = true;
                inters_node = list1;
            }
            list2 = list2.next;
            elem2++;
        }
        list1 = list1.next;
        elem1++;
    }

    
    // Compare tails of lists for equality
    while (list1 != null && intersect == true) {
        if (list1.data != list2.data || list1.next != list2.next) 
                intersect = false;
        list1 = list1.next;
        list2 = list2.next;
    }
       
    // Print results
    if (intersect == true) {
        System.out.println("\n\nThe lists intersect at node with value " + inters_node.data + " (k1 = " + 
                           elem1 + ", k2 = " + elem2 + ")");
    } else {
        System.out.println("\n\nThe lists do not intersect");
    }  
    
}

// D. Scott
// CCI - Problem 2.7
// Determine whether two singly linked lists intersect

class Node {
    Node next = null;
    int data;
    
    public Node(int d) {
        data = d;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

public static void main (String[] args)
{
    // Generate lists
    Node list1 = new Node(5);
    Node head1 = list1;
    list1.appendToTail(3);
    list1.appendToTail(8);
    list1.appendToTail(6);
    list1.appendToTail(2);
    list1.appendToTail(15);
    list1.appendToTail(9);
    list1.appendToTail(3);
    
    Node list2 = new Node(12);
    Node head2 = list2;
    list2.appendToTail(16);
    list2.appendToTail(4);
    list2.appendToTail(5);
    list2.appendToTail(9);
    list2.appendToTail(17);
    list2.appendToTail(12);
        
    System.out.println("List 1:");
    while (list1 != null) {
        System.out.print(list1.data + " ");
        list1 = list1.next;
    }
    System.out.println("\n\nList 2:");
    while (list2 != null) {
        System.out.print(list2.data + " ");
        list2 = list2.next;
    }
      
    list1 = head1;
    list2 = head2;
    
    boolean intersect = false;
    Node inters_node = new Node(0);
    int elem1 = 0;
    int elem2 = 0;
    // Compare lists for intersection node
    while (list1 != null && intersect == false) {
        list2 = head2;
        elem2 = 0;
        while (list2 != null && intersect == false) {
            if (list1.data == list2.data && list1.next == list2.next) {
                intersect = true;
                inters_node = list1;
            }
            list2 = list2.next;
            elem2++;
        }
        list1 = list1.next;
        elem1++;
    }

    
    // Compare tails of lists for equality
    while (list1 != null && intersect == true) {
        if (list1.data != list2.data || list1.next != list2.next) 
                intersect = false;
        list1 = list1.next;
        list2 = list2.next;
    }
       
    // Print results
    if (intersect == true) {
        System.out.println("\n\nThe lists intersect at node with value " + inters_node.data + " (k1 = " + 
                           elem1 + ", k2 = " + elem2 + ")");
    } else {
        System.out.println("\n\nThe lists do not intersect");
    }  
    
}