Union of Two Linked Lists Java

PROGRAM TO FIND THE UNION AND INTERSECTION OF TWO LINKED LISTS

class LinkedList {

    Node head; // head of list

 

    /* Linked list Node*/

    class Node {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

 

    /* Function to get Union of 2 Linked Lists */

    void getUnion(Node head1, Node head2)

    {

        Node t1 = head1, t2 = head2;

 

        // insert all elements of list1 in the result

        while (t1 != null) {

            push(t1.data);

            t1 = t1.next;

        }

 

        // insert those elements of list2

        // that are not present

        while (t2 != null) {

            if (!isPresent(head, t2.data))

                push(t2.data);

            t2 = t2.next;

        }

    }

 

    void getIntersection(Node head1, Node head2)

    {

        Node result = null;

        Node t1 = head1;

 

        // Traverse list1 and search each

        // element of it in list2.

        // If the element is present in

        // list 2, then insert the

        // element to result

        while (t1 != null) {

            if (isPresent(head2, t1.data))

                push(t1.data);

            t1 = t1.next;

        }

    }

 

    /* Utility function to print list */

    void printList()

    {

        Node temp = head;

        while (temp != null) {

            System.out.print(temp.data + " ");

            temp = temp.next;

        }

        System.out.println();

    }

 

    /*  Inserts a node at start of linked list */

    void push(int new_data)

    {

        /* 1 & 2: Allocate the Node &

                  Put in the data*/

        Node new_node = new Node(new_data);

 

        /* 3. Make next of new Node as head */

        new_node.next = head;

 

        /* 4. Move the head to point to new Node */

        head = new_node;

    }

 

    /* A utilty function that returns true

       if data is present in linked list

       else return false */

    boolean isPresent(Node head, int data)

    {

        Node t = head;

        while (t != null) {

            if (t.data == data)

                return true;

            t = t.next;

        }

        return false;

    }

 

    /* Driver program to test above functions */

    public static void main(String args[])

    {

        LinkedList llist1 = new LinkedList();

        LinkedList llist2 = new LinkedList();

        LinkedList unin = new LinkedList();

        LinkedList intersecn = new LinkedList();

 

        /*create a linked lits 10->15->5->20 */

        llist1.push(20);

        llist1.push(4);

        llist1.push(15);

        llist1.push(10);

 

        /*create a linked lits 8->4->2->10 */

        llist2.push(10);

        llist2.push(2);

        llist2.push(4);

        llist2.push(8);

 

        intersecn.getIntersection(llist1.head, llist2.head);

        unin.getUnion(llist1.head, llist2.head);

 

        System.out.println("First List is");

        llist1.printList();

 

        System.out.println("Second List is");

        llist2.printList();

 

        System.out.println("Intersection List is");

        intersecn.printList();

 

        System.out.println("Union List is");

        unin.printList();

    }

}

OUTPUT

 First list is 
10 15 4 20 
 Second list is 
8 4 2 10 
 Intersection list is 
4 10 
 Union list is 
2 8 20 4 15 10

CREDITS: https://www.geeksforgeeks.org/union-and-intersection-of-two-linked-lists/