[数据结构与算法]数据结构之快慢指针的应用

快慢指针

快慢指针就是定义两个指针，这两个指针 动一动速度是一快一慢的，一次来制造出自己想要的差值，这个差值可以让我们找到链表上响应的节点，一般情况下，快指针的移动步长为满指针的两倍。

解决中间值问题

原理

定义两个指针指向链表的头结点处，slow一次移动一个，fast一次移动两个当fast走完后，slow刚好走了链表的一半

代码

public static String getMid(Node<String> first) {
    //定义两个指针
   Node fast = first;
   Node slow = first;
    //使用两个指针遍历链表
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }

    //当快指针指向的节点下一个节点为空时结束

    //满指针指向的节点就是中间值

    return  slow.item.toString();
}

单向链表是否有环问题

原理

快慢指针是一快一慢的，当链表中没有环时，快慢指针不会相遇，有环时会相遇

代码实现

public static boolean isCircle(Node<String> first) {
    //定义快慢指针
   Node<String> fast = first;
   Node<String> slow = first;

    //遍历链表，如果指向了同一个节点就代表有环
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;

        if (fast.equals(slow)) {
            return true;
        }
    }
    return false;
}

有环链表入口问题

原理

当快慢指针相遇时，我们可以判断链表中有环，这是重新设定一个新指针指向链表的七点，且步长和满指针一样为1，则慢指针与新指针下个相遇的地方就是环的入口。

代码实现

public static Node getEntrance(Node<String> first) {
    //首先检测到环
    Node<String> fast = first;
    Node<String> slow = first;
    Node<String> temp = null;

    while (fast != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;

        if (slow.equals(fast)) {
            temp = first;
            continue;
        }
        if (temp != null) {
            temp = temp.next;
            //判断临时指针是否和慢指针相遇
            if (temp.equals(slow)) {
                break;
            }
        }
    }
    return temp;
}