经度算法：花式链表中查找

古城微笑少年丶 2022-02-01 02:59 214阅读 0赞

在面试中有关链表的提问，真可谓经久不衰。说实话笔者对算法也是研究不太深，而大多数人更要注重后天的积累（套路见多了就会了），天才毕竟是少数人。上次谈过[逆转单向链表][Link 1]，今天将分享单链表中查找：是否存在环以及环入口、寻找中位数、倒数第K个节点。

> **快慢指针**
> 
> 快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。

![20190521095720781.png][]

class Node<T> {
    	T value;
    	Node<T> next;
    	Node(T value) {
    		this.value = value;
    	}
    }

**判断单链表是否存在环**

> 思路：如果一个单链表中有环，用一个指针去遍历，永远不会结束，所以可以用两个指针，一个指针一次走一步，另一个指针一次走两步，如果存在环，则这两个指针会在环内相遇，时间复杂度为O(n)。

> 环入口点
> 
> 如果有环，当fast若与slow相遇时，slow肯定没有走遍历完链表或者恰好遍历一圈，于是我们从链表头与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

> 环儿长度
> 
> fast, slow从碰撞点出发再次碰撞就是环儿的长度

public static boolean existRing(Node header) {
        // 定义两个指针fast和slow,fast移动步长为2，slow移动步长为1
        Node fast = header;
        Node slow = header;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            //如果相遇则存在环儿，跳出
            if (fast == slow) {
                break;
            }
        }
        // 根据跳出循环的条件return
        if (fast == null || fast.next == null) {
            return false;
        } else {
            return true;
        }
    }
    public static Node findRingEntrance(Node header) {
        Node fast = header;
        Node slow = header;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = header;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    public static int ringLength(Node header) {
        // 如果不存在环儿，返回0
        if (!isExistLoop(header)) {
            return 0;
        }
        Node fast = header;
        Node slow = header;
        int length = 0;
        boolean begin = false;
        boolean again = false;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 超过两圈后停止计数，跳出循环
            if (fast == slow && again == true) {
                break;
            }
            // 超过一圈后开始计数
            if (fast == slow && again == false) {
                begin = true;
                again = true;
            }
            if (begin == true) {
                ++length;
            }
        }
        return length;
    }

**寻找中位数、倒数第K个节点**

思路大同小异。![Link 1][]

[Link 1]: /images/20220201/8c5fe006c56e405db17522c5e2e1d30e.png
[20190521095720781.png]: /images/20220201/22938409b8904a2fa53174f0b36b3151.png