美文网首页
Floyd循环检测算法 快慢指针的三个例子

Floyd循环检测算法 快慢指针的三个例子

作者: 饱饱想要灵感 | 来源:发表于2023-11-27 22:09 被阅读0次

    算法概述

    Floyd循环检测算法,也被称为龟兔赛跑算法,或者快慢指针,是一种可以在链表或数组等线性结构中使用的技术。

    此技术通过同时使用两个指针,一个快指针和一个慢指针来遍历一个数据结构。通常来说,快指针每次移动两个节点,而慢指针每次只移动一个节点

    它的主要优点是它可以在单次遍历中解决以上的问题,从而使得算法效率高。

    在使用快慢指针时,通常需要注意的是可能出现的边界条件,例如链表为空或只有一个或两个节点的情况。

    三个例子

    1. 找到链表的中点

    首先创建两个指针,slowPtrfastPtr,都初始化为头节点。

    然后,只要fastPtrfastPtr.next不为null,就将fastPtr向前移动两个节点,slowPtr向前移动一个节点。

    fastPtr无法再前进时,slowPtr将位于链表的中点。

    Java实现:

    class Node {
        int data;
        Node next;
      
        Node(int data) {
            this.data = data;
            next = null;
        }
    }
    
    public Node findMiddle(Node head) {
        Node slowPtr = head;
        Node fastPtr = head;
      
        if (head != null) {
            while (fastPtr != null && fastPtr.next != null) {
                fastPtr = fastPtr.next.next;
                slowPtr = slowPtr.next;
            }
        }
      
        return slowPtr;
    }
    
    2. 检测链表中是否有环

    首先创建两个指针,slowfastslow指针每次移动一个节点,fast指针每次移动两个节点。

    如果在某个时刻,slowfast指向同一节点,那么链表中存在环。

    如果fast指针到达链表的末尾(即fastfast.next为null),那么链表中不存在环。

    Java实现:

    class Node {
        int data;
        Node next;
    
        Node(int data) {
            this.data = data;
            next = null;
        }
    }
    
    public boolean hasCycle(Node head) {
        if (head == null) {
            return false;
        }
    
        Node slow = head;
        Node fast = head.next;
    
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
    
        return true;
    }
    
    3. 找到两个链表的交叉点

    找到两个链表交叉点通常包括3个步骤:

    1. 我们将遍历两个链表以确定他们的长度及是否相交。
    2. 我们将使两个指针同时从两个链表的头部开始,但是较长的那个链表的指针会先移动“长度差”的步数。
    3. 两个指针将同时移动,当他们相遇时,那个点就是链表的交叉点。

    Java实现:

      static class ListNode {
            int data;
            ListNode next;
    
            ListNode(int data) {
                this.data = data;
                next = null;
            }
        }
    
        public ListNode getIntersectionListNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
    
            ListNode p1 = headA;
            ListNode p2 = headB;
    
            int length1 = 1;
            int length2 = 1;
    
            // 两个指针移动到尾部
            while (p1.next != null) {
                p1 = p1.next;
                length1++;
            }
            while (p2.next != null) {
                p2 = p2.next;
                length2++;
            }
    
            // 如果尾部不同, 则无交叉点
            if (p1 != p2) return null;
    
            // 将两个指针移动到头部
            p1 = headA;
            p2 = headB;
    
            // 较长的指针先走一段
            int diff = length1 - length2;
            if (diff > 0) {
                for (int i = 0; i < diff; i++) {
                    p1 = p1.next;
                }
            } else if (diff < 0) {
                for (int i = diff; i < 0; i++) {
                    p2 = p2.next;
                }
            }
    
            // 两个指针同时移动, 直到他们相遇
            while (p1 != p2) {
                p1 = p1.next;
                p2 = p2.next;
            }
    
            return p1;
        }
    

    相关文章

      网友评论

          本文标题:Floyd循环检测算法 快慢指针的三个例子

          本文链接:https://www.haomeiwen.com/subject/msdtgdtx.html