判断链表中是否有环以及其中的扩展衍生问题

记录关于链表的面试题

判断单链表中是否有环？

• 直接遍历解法，每遍历一个元素都要和前面遍历过的所有元素进行比较，时间复杂度比较高为O(n^2)

    //使用遍历校验看单链表是否有环，时间复杂度O(n^2) ,空间复杂度O(1)
    public boolean checkIsRing() {
        Node pre;
        Node cur = head;
        while (cur != null) {
            pre = cur;
            cur = cur.next;
            Node compare = head;
            while (compare != null && compare != pre) {
                if (compare == cur) {
                    return true;
                }
                compare = compare.next;
            }
        }
        return false;
    }

• HashMap空间换时间解法

    //使用HashMap保存历史链表，降低时间复杂度O(n) 空间复杂度变为O(n)
    public boolean checkIsRingWithHashMap() {
        HashMap<Node, Integer> store = new HashMap<>();
        Node cur = head;
        int count = 1;
        while (cur != null) {
            if (store.containsKey(cur)) {
                return true;
            }
            store.put(cur, count++);
            cur = cur.next;
        }
        return false;
    }

• 快慢指针，采用追击问题的解决方式来操作。若有环则快指针会和慢指针相遇

    //使用快慢指针 时间复杂度O(n) ,空间复杂度O(1)
    public boolean checkIsRingWithQuickAndSlowNode() {
        Node slow = head;
        Node quick = head;
        while (slow != null && quick != null) {
            slow = slow.next;
            quick = quick.next.next;
            if (slow == quick) {
                return true;
            }
        }
        return false;
    }

有环那么环的长度是多少？

该问题，统计两次相遇之间的遍历次数即可

    //返回单链表的环长度
    public int getRingLength() {
        int cycle = 0;
        int count = 0;
        Node slow = head;
        Node quick = head;
        while (quick != null && quick.next != null) {
            slow = slow.next;
            quick = quick.next.next;
            count++;
            if (slow == quick) {
                if (cycle == 1) {
                    return count;
                }
                cycle++;
                count = 0;
            }
        }
        return 0;
    }

环的起始节点是什么？

这个问题不好想到关联关系，为了解释，引用<漫画算法>里面的一张图

判断环的起始节点
由图我们我们很简单的可以通过行走的距离得到2(D+S1)=D+2S1+S2，从而得到一个重要结论，那就是D=S2，也就是头结点到入环节点的位置等于首次相遇到入环点的位置，那么我们只要在相遇的时候，将任一节点移动到头结点，然后快慢指针速度变为1即可，下面为实现源码

    //获取入环节点
    public Node getRingStartNode() {
        Node slow = head;
        Node quick = head;
        while (quick != null && quick.next != null) {
            slow = slow.next;
            quick = quick.next.next;
            if (slow == quick) {
                //相遇了,让slow到头结点
                slow = head;
                break;
            }
        }

        if (quick != null && quick.next != null) {
            while (slow != quick) {
              //修改快慢节点的速度
                slow = slow.next;
                quick = quick.next;
            }
        }
        return slow;
    }