快慢指针思想(Hare & Tortoise 算法)

目录​​​​​​​

一、快慢指针概念

二、常用场景

 2.1 寻找倒数第k个节点

2.2 判断回文链表

2.3 用于判断链表中是否存在 “环”  

2.4 用于判断存在“环”的链表中，“环”的起始位置

---

一、快慢指针概念

        快慢指针是一种常用的数据结构思想，主要用于解决链表中的问题。

        该算法会使用两个移动速度不同的指针，一个快指针和一个慢指针。

---

二、常用场景

 2.1 寻找倒数第k个节点

 主要逻辑：

• 假设寻找倒数第k个节点，
• 快指针先走k步，
• 然后快慢指针一起走，
• 当快指针走到null时，慢指针就指向要找的那个节点。

代码实现： 

    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode fast = pHead;
        while(k > 0){
            if(fast == null){ //处理k值大于链表长度的问题；
                return null;
            }
            fast = fast.next;
            k--;
 
        }
        ListNode slow = pHead;
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

---

2.2 判断回文链表

 主要逻辑：

• 使用快指针找到链表的中间节点，
• 逆序后半部分节点，
• 快慢指针一起移动，并在移动时对比各自指向的元素是否内容一致。

代码实现：

    public class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public boolean isPail (ListNode head) {
        if (head == null) {
            return true;
        }
        
        //设置快慢两个指针；
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        } //走完这个循环，slow指向中间节点；
 
        fast = head; //重新获得头节点；
        slow = reverse(slow); //逆序链表后半段；
 
        //两个指针同时走，直到slow为空；
        while(slow != null){
            //出现值不同，则直接返回false；
            if(fast.val != slow.val){
                return false;
 
            }
            fast = fast.next;
            slow = slow.next;
        }
 
        return true;
    }
    private ListNode reverse(ListNode cur) {
        ListNode prev = null;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }

---

2.3 用于判断链表中是否存在 “环”  

主要逻辑：

• 快指针每次移动两个节点，慢指针每次移动一个节点，
• 当快慢两个指针相遇时，则表示存在环，
• 当快指针指向null，或快指针的下一节点指向null时，则不存在环。

代码实现： 

    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }

---

2.4 用于判断环形链表中，“环”的起始位置

主要逻辑：

• 快指针每次移动两个节点，慢指针每次移动一个节点，
• 当快慢两个指针相遇时，将其中一个指针重置为链表的头节点，
• 两个指针同时每次移动一个节点，
• 当两个节点相遇时，相遇的位置就是环的起始位置。

代码实现： 

    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        
        ListNode fast = head;
        ListNode slow = head;
 
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                slow = head;
                while(true){
                    if(fast == slow){
                        return fast;
                    }
                    fast = fast.next;
                    slow = slow.next;
                }
            }
        }
        return null;
    }

---

（ 哈哈哈~~ 文章结束！） 

（ 看到这里，如果有为各位帅哥美女提供一点点灵感，请点一个小小的赞哦，比心💖💖💖 ）