public class Main {

    public static void main(String[] args) throws NullPointerException {
        Node list1 = new Node();
        list1.insert_node_at_end(10);
        list1.insert_node_at_end(20);
        list1.insert_node_at_end(30);
        list1.insert_node_at_end(40);
        list1.print();
        Node list2 = new Node();
        list2.insert_node_at_end(10);
        list2.insert_node_at_end(15);
        list2.insert_node_at_end(30);
        list2.insert_node_at_end(40);
        list2.insert_node_at_end(60);
        list2.print();
    Node ret = merge_two_lists(list1, list2);
    ret.print();
    }
    public static Node merge_two_lists(Node tmpA, Node tmpB) {
        Node A = tmpA.head;
        Node B = tmpB.head;
        System.out.println(A.info);
        Node ret = new Node();
        while(A != null && B != null) {
            if(A == null || B == null) {
                break;
            }
            if(A.info <= B.info) {
                ret.insert_node_at_end(A.info);
                A = A.next;
            }
            else {

                ret.insert_node_at_end(B.info);
               B = B.next;
            }
        }
        while(A != null) { // if A is larger than B, continue reversing it
            ret.insert_node_at_end(A.info);
            A = A.next;
        }
        while(B != null) { // if B is larger than A, continue reversing it
            ret.insert_node_at_end(B.info);
            B = B.next;
        }
        return ret;
    }

}

class Node {
    Node head; // first node in the List
    Node next;
    int info; // storing bunch of integers
    Node() {
        head = null;
        next = null;
    }
    Node(int x) {
        info = x;
        next = null;
    }
    public void insert_node_at_beginning(int x) { // data which the new node will store
        if(head == null) { // empty linked list
            head = new Node(x);
            return;
        }
        Node new_node = new Node(x);
        new_node.next = head;
        head = new_node;
    }
    public void insert_node_at_end(int x) { // at the end insert a node
        Node new_node = new Node(x);
        if(head == null) {
            head = new_node;
            head.next = null;
            return;
        }
        Node tmp = head;
        while(tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = new_node;
        new_node.next = null;
    }
    public void delete_node(int x) { // data which should get deleted
        Node tmp = head;
        Node prev = null; // previous node
        while(tmp.info != x) { // iterate through the list till the node which should get deleted
            prev = tmp;
            tmp = tmp.next;
        }
        prev.next = tmp.next;
    }
    public void print() {
        Node tmp = head;
        while(tmp != null) {
            System.out.print(tmp.info + "-> ");
            tmp = tmp.next;
        }
        System.out.println();
    }

}