leetCode-单链表查找环问题

题目描述：

• 给定一个链表，判断链表中是否有环。不使用额外空间解决
• 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
• 求有环单链表的环长
• 求有环单链表的链表长
• 如何判断两个单链表有交？第一个交点在哪里？

image

给定一个链表，判断链表中是否有环。不使用额外空间解决

使用slow和fast两个指针遍历链表，fast的比slow快一步，当fast遍历不为null，并且fast==slow则说明单链表中存在环；

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

image

Pos:为slow和fast第一的交点；
Join：链表开始入环的第一个结点；
x：Join到Pos的距离；
LenA： head到join的距离
R : 环的长度
第一次相遇slow走的距离：S = LenA + x；
第一次相遇fast走的距离：2S = LenA + x + nR；
由此可以得出： LenA = nR - x；
第一次碰撞点Pos到连接点Join的距离 + nR=头指针到连接点Join的距离*
因此算法为：当slow与fast第一次相遇后，将slow指向head结点，然后slow与fast以同样的速度依次遍历，再次相遇时slow指向的结点就是链表开始入环的结点

求有环单链表的环长

在环上相遇后，记录第一次相遇点为Pos，之后指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。

求有环单链表的链表长

Head遍历到Join的距离 + 环长 = 链表长

如何判断两个单链表有交点？第一个交点在哪里？

如果两个链表相交，那么他们最后一个结点一定相同；否则不相交； 由此可以遍历两个链表，拿到最后一个结点做对比，相同则相交，不同则不相交；

判断出两个链表相交后就是判断他们的交点了。假设第一个链表长度为len1，第二个问len2，然后找出长度较长的，让长度较长的链表指针向后移动|len1 - len2| (len1-len2的绝对值)，然后在开始遍历两个链表，判断节点是否相同即可

参考

判断两个链表是否相交并找出交点

求有环单链表中的环长、环起点、链表长

实现代码

     // 判断单链表中是否存在环
    public boolean hasCycle(ListNode head) {
        boolean flag = false;
        ListNode fast = head;
        ListNode slow = head;
        while (fast !=null && fast.next !=null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                flag = true;
                break;
            }
        }
        return flag;
    }

     // 获取单链表第一次入环的结点
    public ListNode getFirstNodeInCycle(ListNode head) {
        if(head == null) {
            return null;
        } else {
            ListNode fast = head;
            ListNode slow = head;
            while(fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if(fast == slow){
                    //有环，则返回环的第一个节点
                    slow = head;
                    while(slow != fast){
                        slow = slow.next;
                        fast = fast.next;
                    }
                    return slow;
                }
            }
            return null;
        }
    }

    // 求环的长度
    public int cycleLength(ListNode head) {
        int meet = 0;
        int length = 0;
        ListNode fast = head;
        ListNode slow = head;
        while (fast !=null && fast.next !=null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow && meet==0) {
                meet ++;
            }
            if (meet == 1){
                length ++;
            }
            if (meet  == 2){
                break;
            }
        }
        return length;
    }
}
class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val = x;
        next = null;
    }
}