快慢指针算法与应用

骑猪看日落 2022-04-01 06:48 188阅读 0赞

## 基本概念 ##

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

## 应用 ##

**1.判断单链表是否为循环链表（Leetcode-141）**  
让快慢指针从链表头开始遍历，快指针向前移动两个位置，慢指针向前移动一个位置;如果快指针到达NULL，说明链表以NULL为结尾，不是循环链表。如果 快指针追上慢指针，则表示出现了循环。

public class Solution {
        public boolean hasCycle(ListNode head) {
            
            ListNode first = head;
            ListNode second = head;
            
            while(second!=null && second.next != null){
                first = first.next;
                second = second.next.next;
                if(first == second){
                    return true;
                }
            }
            return false;
        }
    }

**2.在有序链表中寻找中位数(Leetcode-876)**  
该方法在不借助计数器变量实现寻找中位数的功能。原理是：快指针的移动速度是慢指针移动速度的2倍，因此当快指针到达链表尾时，慢指针到达中点。程序还要考虑链表结点个数的奇偶数因素，当快指针移动x次后到达表尾（1+2x），说明链表有奇数个结点，直接返回慢指针指向的数据即可。如果快指针是倒数第二个结点，说明链表结点个数是偶数，这时可以根据“规则”返回上中位数或下中位数或（上中位数+下中位数）的一半。

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

**3.两个单链表相交的起始节点(Leetcode-160)**

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        
        /**
         * 链表向交，尾节点相等
         *   A:          a1 → a2
         *                      ↘
         *                        c1 → c2 → [c3]相等节点
         *                      ↗            
         *   B:     b1 → b2 → b3
         *
         * 相交的位置为 :
         * diff = 长链表长度-短链表长度 ,长链表先走diff长度，之后一起走，判断节点是否相等
         */
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if(headA == null || headB == null){
                return null;
            }
                
            ListNode iteratorA = headA;
            ListNode iteratorB = headB;
            int lenA = 0;
            int lenB = 0;
            while(iteratorA!=null||iteratorB!=null){
                
                if(iteratorA!=null){
                    lenA++;
                    iteratorA = iteratorA.next;
                }
                if(iteratorB!=null){
                    lenB++;
                    iteratorB = iteratorB.next;
                }
                
            }
            iteratorA = headA;
            iteratorB = headB;
            if(lenA>lenB){
                int diff = lenA - lenB;
                while(diff>0){
                     iteratorA = iteratorA.next;
                    diff--;
                }
            }else{
                int diff = lenB - lenA;
                 while(diff>0){
                     iteratorB = iteratorB.next;
                     diff--;
                }
            }
            while(iteratorA!=null){
                if(iteratorA==iteratorB){
                    return iteratorA;
                }
                iteratorB = iteratorB.next;
                iteratorA = iteratorA.next;
            }
            return null;
        }
    }