剑指offer55：链表中环的入口节点

题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

tips：

1.关于==和equals

    1）对于==，如果作用于基本数据类型的变量，则直接比较其存储的 “值”是否相等；

　　　　如果作用于引用类型的变量，则比较的是所指向的对象的地址

    2）对于equals方法，注意：equals方法不能作用于基本数据类型的变量

　           equals方法是基类Object中的方法，因此对于所有的继承于Object的类都会有该方法

　　　　如果没有对equals方法进行重写，则比较的是引用类型的变量所指向的对象的地址；

　　　　诸如String、Date等类对equals方法进行了重写的话，比较的是所指向的对象的内容。

在Java中游8种基本数据类型：

　　浮点型：float(4 byte), double(8 byte)

　　整型：byte(1 byte), short(2 byte), int(4 byte) , long(8 byte)

　　字符型: char(2 byte)

详见：https://www.cnblogs.com/dolphin0520/p/3592500.html

2. 

        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node7 = new ListNode(2);

        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node7;
        System.out.println(node2.equals(node7)+"\t"+node2+"\t"+node7+"\t"+node7.next);
        node7.next=node3;
        System.out.println(node2.equals(node7)+"\t"+node2+"\t"+node7+"\t"+node7.next);
//        即使node2和node7的val相同，next指向相同，但是他们的地址不同，node7不是node2的复制/对象的引用（浅拷贝node7=node2）;

代码：

//    hash版本，仅判断hash.containsKey(node)是否存在这个节点进行
    public static ListNode EntryNodeOfLoop1(ListNode pHead){
            ListNode node = pHead;

            HashMap<ListNode,Boolean> map = new HashMap<>();

            while(node!=null){
                if(map.containsKey(node)){
                    return node;
                }else{
                    map.put(node,true);
                    node = node.next;
                }
            }

            return null;
    }


    //    两个指针，一快一慢，若快的追上慢的，则存在换，否则null。若存在，则从相遇的节点开始（此节点在环内）计数，再次相遇为环的节点个数
    public static ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null) {
            return pHead;
        }

        ListNode last = pHead;
        ListNode fast = pHead.next==null?null:pHead.next;
//        只要出现null节点，则不存在环，返回null
        while (fast != last  ) {
            if (fast.next != null&&last.next!=null) {
                fast = fast.next.next;
                last = last.next;
            }else {
                return null;
            }
        }
//        计算环的长度count，不一定需要
//        if (fast == last) {
//            int count = 0;
//            while (count==0||fast != last) {
//                if (fast.next != null) {
//                    fast = fast.next.next;
//                }
//                last = last.next;
//                ++count;
//            }
//            fast = pHead;
//            last = pHead;
//            while (count > 0) {
//                fast = fast.next;
//                --count;
//            }
//            while (fast != last) {
//                fast = fast.next;
//                last = last.next;
//            }
//            return fast;
//        }
//        慢，出不来
        fast=pHead;
        while (fast!=last){
            fast=fast.next;
            last=last.next;
        }
        return last;
    }