从零上手双指针

先分享一个很有意思的视频 https://www.bilibili.com/video/BV1Ku411z7VT

算法数据结构这类课程的博客做起来不太方便

t83，t26，这两道题目，一个场景是链表，一个场景是数组可以说十分有代表性

先看链表题型

总体思路的注意点一共有三个

1. 快指针停止的终止条件
2. 判断快慢指针是否相等
3. 快慢指针值不相等时如何操作

主要是第三点的不一样，重点关注下这一点，我一开始其实也不太容易想明白，我的办法是，找一个中间状态来看

最后有一点需要注意的是，需要把slow.next清空，考虑存在情况

/**
 * 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 ListNode deleteDuplicates(ListNode head) {
        if(head==null) return null;
        ListNode slow = head, fast = head;
        while(fast!=null){
            if(fast.val!=slow.val){
                slow.next = fast;
                slow = slow.next;
            }
            fast = fast.next;
        }
        // 设置 slow.next 为null
        slow.next = null;
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

这题的关键在于首先在于原地修改，我们常规的思路是做不到原地修改的，我们不能再去创建一个新的数组

其次由于数组存储的特点我们在删除元素的时候，如果删除一个元素以后把后面的元素往前挪，时间复杂度会大很多

这个时候就要用到我们的双指针了，也是和链表中写到的快慢指针用法类似

同样关注不重复的时候，如何操作

class Solution {
    public int removeDuplicates(int[] nums) {
        // 考虑空数组的运行结果
        if(nums.length==0) return 0;
        int slow=0, fast = 0;
        while(fast<nums.length) {
            // 不重复
            if(nums[fast]!=nums[slow]){
                slow++;
                nums[slow]=nums[fast];
            }
            // 重复
            fast++;
        }
        return slow+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

贴下代码