【基础算法】快慢双指针

1. 链表相关问题
   • 判断链表是否有环
     • 应用场景：在处理链表数据结构时，例如在垃圾回收算法（检测引用是否形成循环）、资源管理（避免循环依赖）等场景中，需要判断链表是否存在环。
     • 实现原理：使用快慢双指针同时从链表头开始遍历。快指针每次移动两步，慢指针每次移动一步。如果链表有环，快指针最终会追上慢指针；如果快指针先到达链表末尾（null），则说明链表无环。
     • 示例代码（以 Java 为例）：

   • class ListNode {
         int val;
         ListNode next;
         ListNode(int val) {
             this.val = val;
         }
     }
     public class LinkedListCycleDetection {
         public boolean hasCycle(ListNode head) {
             if (head == null) {
                 return false;
             }
             ListNode slow = head;
             ListNode fast = head;
             while (fast!= null && fast.next!= null) {
                 slow = slow.next;
                 fast = fast.next.next;
                 if (slow == fast) {
                     return true;
                 }
             }
             return false;
         }
     }

     • 寻找链表中环的入口节点
       • 应用场景：在发现链表有环后，进一步确定环的起始位置，这在分析循环数据结构的起点或者循环依赖的根源时很有用。
       • 实现原理：当快慢指针相遇后，将慢指针重新指向链表头，然后快慢指针同时以相同速度移动，再次相遇的节点就是环的入口节点。
       • 示例代码（以 Java 为例）：

       • class ListNode {
             int val;
             ListNode next;
             ListNode(int val) {
                 this.val = val;
             }
         }
         public class LinkedListCycleEntry {
             public ListNode detectCycle(ListNode head) {
                 if (head == null) {
                     return null;
                 }
                 ListNode slow = head;
                 ListNode fast = head;
                 boolean hasCycle = false;
                 while (fast!= null && fast.next!= null) {
                     slow = slow.next;
                     fast = fast.next.next;
                     if (slow == fast) {
                         hasCycle = true;
                         break;
                     }
                 }
                 if (!hasCycle) {
                     return null;
                 }
                 slow = head;
                 while (slow!= fast) {
                     slow = slow.next;
                     fast = fast.next;
                 }
                 return slow;
             }
         }

         • 寻找链表的中间节点
           • 应用场景：在对链表进行分割、归并排序或者在一些需要平衡处理链表两侧节点的算法中，找到链表的中间节点很重要。
           • 实现原理：快指针每次移动两步，慢指针每次移动一步。当快指针到达链表末尾时，慢指针正好在链表的中间位置。
           • 示例代码（以 Java 为例）：

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}
public class LinkedListMiddleNode {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast!= null && fast.next!= null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}