随笔，算法(五) 快慢指针

快慢指针方法也被称为 Hare & Tortoise 算法，该算法会使用两个在数组（或序列/链表）中以不同速度移动的指针。

该方法在处理循环链表或数组时非常有用。

例题

1，环形链表

来自LeetCode 141

解法

1，哈希表

有空再补吧。哈希表忘差不多了哈哈哈。

2，快慢指针

将两个指针置于相同的位置，赋予后指针更慢的数字，前指针更快的速度。
如果非环，则到null都永远碰不上。
如果是环，则迟早会撞上。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null){
            return false;
        }
        ListNode fr = head;
        ListNode be = head.next;
        while(fr!=be){
            if(fr==null||be==null)
                return false;
            fr = fr.next;
            if(be.next==null)
                return false;
            be = be.next.next;
        }
        return true;
    }
}

理解

1，对于链表题，总要涉及next，本题因为速度不同，出现next.next，这样就必须要考虑前一个next为空对象的情况。

2,链表中倒数第k个节点

来自剑指offer22.

这道题是快慢指针的智力用法，想到思路就很容易解决。

解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fr = head;
        ListNode be = head;
        for(int i = 0;i<k;i++){
            if(be.next==null)
                return head;
            be = be.next;
        }
        while(be!=null){
            fr=fr.next;
            be=be.next;
        }
        return fr;
    }
}

理解

1，思路很重要！！！

2，链表应该优先想到双指针和迭代，快慢指针是双指针中很基础的解法。

3,回文链表

来自LeetCode234

本题掌握非常差，务必重新做一次！！！！！

解法

1，快慢指针 + 栈

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next==null)
            return true;
        ListNode fr = head;
        ListNode br = head;
        ListNode cur = null;
        Stack<ListNode> stack = new Stack<ListNode>();
        while(br!=null){
            stack.push(fr);
            cur = fr;
            fr = fr.next;
            if(br.next==null){
                br = null;
                stack.pop();
                fr = cur;
            }
            else if(br.next.next!=null)
            br = br.next.next;
            else{
                br = null;
                fr = cur;
            }
        }
        fr = fr.next;
        while(fr!=null){
            ListNode a = stack.peek();
            if(fr.val != a.val)
                return false;
            stack.pop();
            fr = fr.next;
        }
        return stack.isEmpty();
    }
}

快慢指针：用于寻找中点

前指针和后指针同时位于head，前指针next速度，后指针next.next的速度。
当后指针为null或者next为空时，前指针到中点。
这是快慢指针的常见用法。

栈：懂得都懂。

理解

本题快慢指针的中点查找的边界值，俺的算法有巨大问题，务必重新研究一遍！！！！！！！！！。