public class Code07 {
    public static class Node<V> {
        public V value;
        public Node<V> last;
        public Node<V> next;
        public Node() {
        }
        public Node(V v) {
            value = v;
            last = null;
            next = null;
        }
    }
    public static void print(Node head){
        while (head != null){
            System.out.print(head.value+" ");
            head = head.next;
        }
    }


    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(8);
        Node node3 = new Node(11);
        Node node4 = new Node(14);

        Node node5 = new Node(1);
        Node node6 = new Node(16);
        Node node7 = new Node(19);

        node1.next=node2;
        node2.next=node3;
        node3.next = node4;

        node5.next = node6;
        node6.next = node7;
        Node ret = mergeLinkList(node1,node5);
        print(ret);
    }

    /**
     * 精髓就是谁大谁不动
     * @param node1
     * @param node2
     * @return
     */
    private static Node mergeLinkList(Node node1, Node node2) {
        if(node1 == null) {
            return node2;
        }
        if(node2 == null) {
            return node1;
        }
        Node<Integer> head = null;
        Node<Integer> curA = node1;
        Node<Integer> curB = node2;
        if(curA.value<=curB.value){
            head = curA;
        }else{
            head = curB;
        }
        Node curMin = null;
        while (true){
            if (curA.value<=curB.value){
                curMin = curA;
                curA = curA.next;
                curMin.next =curA;
            } else {
                curMin = curB;
                curB = curB.next;
            }
            if(curA == null && curB == null){
                return head;
            } else if (curA == null && curB != null){
                curMin.next = curB;
                return head;
            }else if (curB == null && curA != null){
                curMin.next = curA;
                return head;
            }
        }
    }

    private static int length(Node node){
        int length = 0;
        while (node != null){
            length++;
            node = node.next;
        }
        return length;
    }
}