快慢指针的应用

什么是快慢指针：快慢指针是链表操作中的常用操作，最经典的应用是判断单链表中是否有环。

判断单链表是否存在环

两个指针fast和slow，fast一次移动两次，slow一次移动一次，如果链表存在环，这两个指针一定会在某个节点碰头。请看下图，一共6次循环让快慢指针相遇。

一段代码解释：

public static boolean hasLoop(SingleNode node) {
        if (node == null || node.getNext() == null) {
            return false;
        }
//快指针移动两次，初始化到next
        SingleNode fast = node.getNext();
        SingleNode slow = node;
        while (fast != null) {
//快慢指针相遇，说明有环
            if (fast == slow) {
                return true;
            }
            if (fast.getNext() != null) {
                fast = fast.getNext().getNext();
            } else {
//快指针的next为null，说明没有环
                return false;
            }
            slow = slow.getNext();
        }
        return false;
    }

当然，快慢指针不止只能判断单链表是否有环，还有一些其他的应用，这里我们列举几个

单链表是否存在环，如果存在，找到环入口。

思路：还是上面检测是否有环的快慢指针，如果有环则快慢指针相遇，相遇后快指针指向head，然后快慢指针都变成每次移动一步，相遇的地方就是入口。
这其实是个数学问题，我们用下面的图来解释。

我们知道fast走两步，slow走一步，按照上图，fast跟slow在K点第一次相遇，这个时候：快慢指针分别走了多少步呢？

slow=a+b
fast=a+b+c+b

而且我们知道fast走了slow的两倍:

fast=slow*2

结合上面两个推论 a+b+c+b=(a+b)*2 => a=c
我们能得到a=c，也就是绿线跟红线一定是相等的。
所以快慢指针第一次相遇的时候，让快指针或者一个新的指针从head出发，两指针以相同的速度出发，一定能在入口相遇。

/**
     * 判断是否有环，如果有得到入口
     * 思路：如果有环，快慢指针会相遇，这时候把快指针赋值给head，快慢指针同时加一，相遇的时候就是指针入口
     *
     * @param root head
     * @return 入口Node
     */
    private SingleNode getEntrance(SingleNode root) {
        SingleNode fast = root;
        SingleNode slow = root;
        boolean front = false;
        while (fast != null && fast.getNext() != null) {
            fast = fast.getNext().getNext();
            slow = slow.getNext();
            if (fast == slow) {
                front = true;
                break;
            }
        }
        if (!front) {
            return null;
        }
        slow = root;
        while (slow != fast) {
            slow = slow.getNext();
            fast = fast.getNext();
        }
        return fast;
    }

在有序链表中寻找中位数

快指针走两步，慢指针走一步，当快指针到达尾节点的时候，慢指针到达中间。

public SingleNode middleNode(SingleNode head) {
        if (head == null) return null;
        SingleNode fast = head, slow = head;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == null) {
                return slow;
            }
        }
        return slow;
    }

输出链表中的倒数第K个节点(即正数第length-K个节点)

/**
     * 输出链表中的倒数第K个节点(即正数第n-K个节点)
     * 思路：两个指针，指针一先走k个node，指针二开始走，指针一到尾部的时候，指针二到达倒数第k个节点
     *
     * @param node 目标链表的头结点
     * @param k    需要找的节点
     * @return 节点
     */
    public SingleNode getReverseNumK(SingleNode node, int k) {
        if (k >= NodeUtil.getLinkedListLength(node)) {
            return null;
        }
        SingleNode fastNode = node;
        SingleNode slowNode = node;
        int pointer = 0;
        while (fastNode != null) {
            fastNode = fastNode.getNext();
            if (pointer >= k) {
                slowNode = slowNode.getNext();
            }
            pointer++;
        }
        return slowNode;
    }

判断两个单链表是否相交，如果相交，找到他们的第一个公共节点

这里提供一种思路，两个链表如果有相同的节点说明相交，换句话说两个链表有一段公共部分

如上图所示，链表一(5->6->7->8->9)跟链表二(1->2->3->4->7->8->9)共享了789节点，我们声明两个指针。
指针一遍历56789，结束后再遍历12347
指针二遍历1234789，结束后遍历567
①->5678912347
②->1234789567
我们发现这个时候7节点已经相等了，说明相交了。

/**
     * 判断两个链表是否相交，如果相交得到交点
     * 两个指针分别指向链表1链表2，指针一到结尾后指向链表2，指针二结尾后指向链表1，如果出现重合，说明相交。
     *
     * @param leftList  链表1
     * @param rightList 链表2
     */
    private SingleNode getIntersect1(SingleNode leftList, SingleNode rightList) {
        SingleNode pointer1 = leftList;
        SingleNode pointer2 = rightList;
        boolean pointer1End = false;
        boolean pointer2End = false;
        while (pointer1 != null) {
            if (pointer1 == pointer2) {
                return pointer1;
            }

            if (!pointer1End && pointer1.getNext() == null) {
                pointer1End = true;
                pointer1 = rightList;
            } else {
                pointer1 = pointer1.getNext();
            }

            if (!pointer2End && pointer2.getNext() == null) {
                pointer2End = true;
                pointer2 = leftList;
            } else {
                pointer2 = pointer2.getNext();
            }
        }
        return null;
    }