LeetCode刷题实况（三）：双指针算法

双指针算法在做题时经常用到：对于线性的数据结构可使用双指针算法，主要形式为从左向右和两面向中间。

一、从两面向中间：适用于寻秩访问，确定开头秩与结尾秩，根据一定的条件，移动两个指针。多用于向量数据结构。双向链表知道头尾节点也可以。

这里拿《剑指offer》中的“调整数组顺序使奇数排在偶数前”为例
题目链接：调整数组顺序使奇数排在偶数前
代码如下：

class Solution {public int[] exchange(int[] nums) {if(nums.length <= 1) return nums;int first = 0;int last = nums.length - 1;while(first < last){while((nums[first] % 2 == 1) && (first < last)){first++;}while((nums[last] % 2 == 0) && (first < last)){last--;}swap(nums, first, last);}return nums;}public void swap(int[] nums, int first, int last){int temp = nums[first];nums[first] = nums[last];nums[last] = temp;}
}

本题的意思是，将所有的奇数都放在前面，偶数都放在后面。看到这个你想到了什么？快排对不对？这就是快排中排序思想的一个变种。

begin指针开始向后移动，满足一定条件时停止，这样begin指针走过的数据都满足这个条件。然后end指针开始向前移动，满足另一个需求时停止，进行一些操作（当然这两个需求也可以相同，详情可见该题：两数之和）。当begin等于或大于end指针时，退出循环。这样begin走过的路都是满足条件1，end走过的路都满足条件2，不满足的都被交换了。

简单一句话就是通过数据来驱动指针。

二、同向双指针：也叫做快慢指针，通过一个快指针向前遍历，来满足条件，驱动慢指针向前移动。

这里用《剑指offer》中的面试题22来解释
题目链接：链表中倒数的第K个节点

代码如下：

/*** 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) {if(head == null) return head;ListNode low = null;ListNode temp = head;while(k-- > 0){head = head.next;}low = temp;while(head != null){head = head.next;low = low.next;}return low;}
}

这个题惭愧的说，我第一反应是用栈，虽然也能用，但是会慢，时间复杂度是N（链表长度）但是入栈出栈操作，确实相对这个耗费时间。

该题中使用算法的技巧：快慢指针之间满足长度为k的条件，那我们只需要满足当快指针走了k步后，才开始驱动慢指针向前走，当快指针到null时，慢指针刚好到达我们想要的节点。

总结：同向双指针是由快指针触发条件，使慢指针向前移动，只需要快指针遍历一次，即可得到我们想要的结果。

三、总结：无论是单向还是双向双指针，都是有快/左指针去触发一个条件（如上面的偶数或到达第k步）然后来驱动慢指针移动，进而得到我们想要的结果。这里双向可以用单向的方式写。