leetcode中快慢指针相关算法问题

主要有三个

q202快乐数
给定一个正整数，每次将该数替换为它每个位置上数的平方和，重复这个过程直到结果变为1，如果能变为1，这个数就是快乐数。
最朴素的解法：对这个正整数每个位置的上的数字求平方并求和，直到结果变为1。但这种解法存在问题：如果这个数不是快乐数，就陷入死循环中，这并不是我们想看到的，结合本文主题，可使用快慢指针。
快慢指针解法：首先我们需要写一个对每个位置上的数字求平方并求和的函数:

private int bitSquareSum(int n) {
   int sum = 0;
   while (n > 0) {
       int bit = n % 10;
       sum += bit * bit;
       n = n / 10;
   }
   return sum;
}

然后我们使用快慢指针：

public boolean isHappy(int n) {
        int slow = n;
        int fast = n;
        do {
            slow = bitSquareSum(slow);
            fast = bitSquareSum(fast);
            fast = bitSquareSum(fast);
        } while (slow != fast);

        return slow == 1;
    }

使用快慢指针思想，slow每次做一次bitSquareSum，fast做两次。
若可以变为1，则必fast先为1，返回true。
若为无限循环，fast每次多做一次bitSquareSum。
假设fast做2n次bitSquareSum后出现循环，则slow必刚好做了n次，并且此时fast与slow相等。
若fast与slow相等了，则说明出现了循环，返回false。

141 环形链表
判断一个链表是否存在环。
若链表存在环，则必定有两个指针指向同一个节点
在这里，我们假设slow=head,fast=head.next,slow每次向前走一步，fast每次向前走两步，即快指针每次都比满指针多走一步，只要这个链表有环，快指针必定会追上慢指针。

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

在这里思考一个问题，为什么每次快指针都是比慢指针多走一步，两步，三步可以吗?
这里追上可以包括两种意思，一是正好碰到，二是超过。
只要两者有速度差，并且链表有环，快指针追上慢指针是必然的事情。fast每次2步，slow每次两步，它们两的距离每次都会增加一步，如果有环，肯定会相遇。而不是超过。

876 链表的中间结点
返回一个链表的中间结点，如果有两个中间结点，则返回第二个中间结点。

public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while(fast.next != null){
            fast = fast.next.next == null? fast.next: fast.next.next;
            slow = slow.next;
        }
        return slow;

    }

slow和fast指针刚开始都指向head节点，fast指针每次走两步，slow指针每次走一步。每次需要判断fast指针是否走到结尾。

总结
当然，以上三个题目肯定存在其他解法比快慢指针解法好。对比一下上面三个题目，发现快指针每次都是比慢指针多走一步。每个题目中具体还需要判断一下临界条件。

leetcode中快慢指针相关算法问题

leetcode中快慢指针相关算法问题

推荐阅读