双指针问题
一、顺序表类型的双指针问题
例1:移除元素
给你一个数组 nums
和一个值 val
,你需要 原地 移除所有数值等于 val
的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1)
额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
方法一:双指针
思路及算法:
由于题目要求删除数组中等于 val
的元素,因此输出数组的长度一定小于等于输入数组的长度,我们可以把输出的数组直接写在输入数组上。可以使用双指针:右指针 right
指向当前将要处理的元素,左指针 left
指向下一个将要赋值的位置。
-
如果右指针指向的元素不等于
val
,它一定是输出数组的一个元素,我们就将右指针指向的元素复制到左指针位置,然后将左右指针同时右移; -
如果右指针指向的元素等于
val
,它不能在输出数组里,此时左指针不动,右指针右移一位。
整个过程保持不变的性质是:区间 [0,left) 中的元素都不等于 val
。当左右指针遍历完输入数组以后,left
的值就是输出数组的长度。
这样的算法在最坏情况下(输入数组中没有元素等于 val
),左右指针各遍历了数组一次。
代码实现:
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
int left = 0;
for (int right = 0; right < n; right++) {
if (nums[right] != val) {
nums[left] = nums[right];
left++;
}
}
return left;
}
}
方法二:双指针优化
思路及算法:
如果要移除的元素恰好在数组的开头,例如序列 [1,2,3,4,5],当 val
为 1 时,我们需要把每一个元素都左移一位。注意到题目中说:「元素的顺序可以改变」。实际上我们可以直接将最后一个元素 5 移动到序列开头,取代元素 1,得到序列 [5,2,3,4],同样满足题目要求。这个优化在序列中 val
元素的数量较少时非常有效。
实现方面,我们依然使用双指针,两个指针初始时分别位于数组的首尾,向中间移动遍历该序列。
如果左指针 left
指向的元素等于val
,此时将右指针 right
指向的元素复制到左指针 left
的位置,然后右指针 right
左移一位。如果赋值过来的元素恰好也等于 val
,可以继续把右指针 right
指向的元素的值赋值过来(左指针 left
指向的等于 val
的元素的位置继续被覆盖),直到左指针指向的元素的值不等于 val
为止。
当左指针 left
和右指针 right
重合的时候,左右指针遍历完数组中所有的元素。
这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。与方法一不同的是,方法二避免了需要保留的元素的重复赋值操作。
代码实现:
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0;
int right = nums.length;
while (left < right) {
// 每次只走一个指针
if (nums[left] == val) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
}
}
例2:删除有序数组中的重复项
给你一个 升序排列 的数组 nums
,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums
的第一部分。更规范地说,如果在删除重复项之后有 k
个元素,那么 nums
的前 k
个元素应该保存最终结果。
将最终结果插入 nums
的前 k
个位置后返回 k
。
不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1)
额外空间的条件下完成。
思路及算法:
首先注意数组是有序的,那么重复的元素一定会相邻。
要求删除重复元素,实际上就是将不重复的元素移到数组的左侧。
考虑用 2 个指针,一个在前记作 p
,一个在后记作 q
,算法流程如下:
1.比较 p
和 q
位置的元素是否相等。
如果相等,q
后移 1 位 如果不相等,将 q
位置的元素复制到 p+1
位置上,p
后移 1 位,q
后移 1 位 重复上述过程,直到 q
等于数组长度。
返回 p + 1
,即为新数组长度。
图解:
代码实现:
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int p = 0;
int q = 1;
while(q < nums.length){
if(nums[p] != nums[q]){
nums[p + 1] = nums[q];
p++;
}
q++;
}
return p + 1;
}
优化:
考虑如下数组:
此时数组中没有重复元素,按照上面的方法,每次比较时 nums[p]
都不等于 nums[q]
,因此就会将 q 指向的元素原地复制一遍,这个操作其实是不必要的。
因此我们可以添加一个小判断,当 q - p > 1
时,才进行复制。
代码实现:
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int p = 0;
int q = 1;
while(q < nums.length){
if(nums[p] != nums[q]){
if(q - p > 1){
nums[p + 1] = nums[q];
}
p++;
}
q++;
}
return p + 1;
}
二、链表类型的双指针问题
例1:移除链表元素
给你一个链表的头节点 head
和一个整数 val
,请你删除链表中所有满足 Node.val == val
的节点,并返回 新的头节点 。OJ链接
思路及算法:
设置前后两个指针。
代码实现:
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return null;
}
ListNode prev = head;
ListNode cur = head.next;
while(cur != null){
if(cur.val == val){
prev.next = cur.next;
cur = cur.next;
}else{
prev = cur;
cur = cur.next;
}
}
// 最后判断第一个节点是否需要删除
if(head.val == val){
head = head.next;
}
return head;
}
}
例2:链表的中间结点
给定一个带有头结点 head
的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。OJ链接
思路及算法:
我们可以先遍历一遍得到 size
,然后第二遍再走 size/2
步即可。
但若要求只能遍历一遍呢?
这时我们可以使用快慢指针法:
代码:
class Solution {
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;
}
}
注意:
while(fast != null && fast.next != null){
这一行代码不能改变判断的先后顺序:
如果把 fast.next != null
放在前面,若 fast == null
,会发生空指针异常!!!
例3:链表中倒数第k个结点
输入一个链表,输出该链表中倒数第k个结点。OJ链接
思路及算法:
我们可以先遍历一遍得到 size
,然后第二遍再走 size - k
步即可。
但若要求只能遍历一遍呢?
这时我们可以使用快慢指针法:
注意:
- 先判断k的合法性。
- 时刻注意避免空指针异常!!!
代码实现:
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(k <= 0 || k > size(head)){
return null;
}
if(head == null){
return null;
}
ListNode slow = head;
ListNode fast = head;
while((k-1) != 0 && fast.next != null){
fast = fast.next;
k--;
}
while (fast.next != null){
slow = slow.next;
fast = fast.next;
}
return slow;
}
public int size(ListNode head){
int count = 0;
ListNode cur = head;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
}
=============================================================================
改进:
判断k的合法性时:
if(k <= 0 || k > size(head)){
这样判断的话,size()方法会先遍历一遍链表,所以我们可以之后再判断上界:
while((k-1) != 0){
fast = fast.next;
if(fast == null){
return null;
}
k--;
}
改进后代码:
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(k <= 0){
return null;
}
if(head == null){
return null;
}
ListNode slow = head;
ListNode fast = head;
while((k-1) != 0){
fast = fast.next;
if(fast == null){
return null;
}
k--;
}
while (fast.next != null){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
例4:链表的回文结构
思路: 将中间节点后的所有节点逆置,两边同时向中间走进行比较。
- 用快慢指针法找到中间节点
slow
。 - 用头插法进行后半段逆序:(下图是逆序后)
然后两边同时向中间走进行比较:
写完后提交代码,我们发现并不能通过,这是因为偶数个数节点情况下会出现问题!!!
各走两步后:
出现了错误!!!
所以,在判断回文的代码中,我们需要加入:
代码:
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
// write code here
// null:不是回文
if(A == null){
return false;
}
// 一个节点:是回文
if(A.next == null){
return true;
}
// 找中间节点:
ListNode slow = A;
ListNode fast = A;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
// 开始反转后半链表:
ListNode cur = slow.next;
while(cur != null){
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
// 开始判断回文:
ListNode head = A;
while(head != slow){
if(head.val != slow.val){
return false;
}
// 偶数个数节点时需要判断:
if(head.next == slow){
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}
}
例5:判断是否有环
给定一个链表,判断链表中是否有环。
OJ链接
思路:
快慢指针,即慢指针一次走一步,快指针一次走两步,两个指针从链表其实位置开始运行,如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。
代码:
public class Solution {
public boolean hasCycle(ListNode head) {
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;
}
}
【扩展问题】:
- 为什么快指针每次走两步,慢指针走一步可以?
假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。当慢指针刚进环时,可能就和快指针相遇了,最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况,因此:在满指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇。 - 快指针一次走3步,走4步,…n步行吗?
在编译器测试时,我们怎么构造出环呢?很简单:
例6:入环节点
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
OJ链接
- 结论:
让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时相遇点的位置开始绕环运行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇。 - 证明:
代码:
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
break;
}
}
if(fast == null || fast.next == null){
return null;
}
ListNode cur = head;
while(cur != slow){
cur = cur.next;
slow = slow.next;
}
return cur;
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/118611.html