/**
 * 链表
 * */



public class test {

    public static void main(String[] args) {
        MyRealLinkedList myRealLinkedList=new MyRealLinkedList();

        myRealLinkedList.addFirst(2);
        myRealLinkedList.addFirst(3);
        myRealLinkedList.addFirst(3);
        myRealLinkedList.addFirst(4);
        myRealLinkedList.display();

      /*  System.out.println("===========================");
        myRealLinkedList.clear();
        myRealLinkedList.display();*/


    }

    //合并两个有序链表
    public static Node mergeTwoLists (Node headA, Node headB){
        if (headA == null) return headB;
        if (headB == null) return headA;
        if (headA == null && headB == null) return null;

        Node newH = new Node(0);
        Node tmp = newH;

        while (headA != null && headB != null) {
            if (headA.val < headB.val) {
                tmp.next = headA;
                headA = headA.next;
            } else {
                tmp.next = headB;
                headB = headB.next;
            }
            tmp = tmp.next;
        }
        if (headB == null) {
            tmp.next = headA;
        }
        if (headA == null) {
            tmp.next = headB;
        }
        return newH;
    }


    //两个链表，找出他们的第一个公共节点
    public static Node getIntersectionNode(Node headA, Node headB) {
        if(headA==null) return null;
        if(headB==null) return null;

        int lenA=0;
        int lenB=0;

        Node pl=headA;
        Node ps=headB;

        while(pl!=null) {
            lenA++;
            pl=pl.next;
        }
        while(ps!=null) {
            lenB++;
            ps=ps.next;
        }
        //走出来pl和ps都为null
        pl=headA;
        ps=headB;
        //<   ==   >
        int len=lenA-lenB;
        //结果：pl永远指向的是长的链表   ps永远指向短的链表   len永远是一个正数
        if(len<0) {
            pl=headB;
            ps=headA;
            len=lenB-lenA;
        }

        while(len!=0) {
            pl=pl.next;
            len--;
        }

        while(pl!=ps) {
            pl=pl.next;
            ps=ps.next;
        }
        //最终都没有相交都返回null，这段代码写不写都没问题
        if(pl==null && ps==null) {
            return null;
        }
        return ps;
    }


    //创造公共节点
    public static void createCute(Node headA, Node headB){
        headB.next.next=headA.next.next;
    }




    public static void main2(String[] args) {

        MyLinkedList myLinkedList=new MyLinkedList();
        //myLinkedList.createList();

        myLinkedList.addLast(1);
        myLinkedList.addLast(3);
        myLinkedList.addLast(5);
        myLinkedList.addLast(7);
        myLinkedList.addLast(9);



        MyLinkedList myLinkedList2=new MyLinkedList();
        //myLinkedList.createList();

        myLinkedList2.addLast(2);
        myLinkedList2.addLast(4);
        myLinkedList2.addLast(6);
        myLinkedList2.addLast(8);
        myLinkedList2.addLast(10);


        Node ret=mergeTwoLists(myLinkedList.head,myLinkedList2.head);
        myLinkedList.show2(ret);
       /* createCute(myLinkedList.head,myLinkedList2.head);
        Node ret=getIntersectionNode(myLinkedList.head,myLinkedList2.head);
        System.out.println(ret.val);*/
    }

    public static void main1(String[] args) {




        System.out.println("hellow word!");
        MyLinkedList myLinkedList=new MyLinkedList();
        //myLinkedList.createList();

        myLinkedList.addLast(1);
        myLinkedList.addLast(2);
        myLinkedList.addLast(3);
        myLinkedList.addLast(4);
        myLinkedList.addLast(5);


        myLinkedList.show();
        System.out.println(myLinkedList.hasCycle());
        //System.out.println(myLinkedList.chkPalindrome());
        //Node ret=myLinkedList.detectCycle();
        //System.out.println(ret.val);
        //Node ret=myLinkedList.deleteDuplication();
        //Node ret=myLinkedList.partition(7);
        //myLinkedList.show();
        //myLinkedList.removeAllKey(5);
        //myLinkedList.show2(ret);

        // myLinkedList.reverseList();



       /* if(headA == null) return headB;
        if(headB == null) return headA;
        if(headA == null && headB == null) return null;

        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;

        while(headA != null && headB != null) {
            if(headA.val<headB.val) {
                tmp.next=headA;
                headA=headA.next;
            }else {
                tmp.next=headB;
                headB=headB.next;
            }
            tmp=tmp.next;
        }
        if(headA==null) {
            tmp.next=headB;
        }
        if(headB==null) {
            tmp.next=headA;
        }
        return newHead.next;*/
    }

}