Leetcode刷题笔记8.12-8.16

19.删除倒数第n个链表结点(8.12)

1. 一个巧妙删除倒数第n个结点的trick

   该方法避免了对链表的一次全面扫描来获得总长度

// 返回链表的倒数第 k 个节点

ListNode findFromEnd(ListNode head, int k) {

ListNode p1 = head;

// p1 先走 k 步

for (int i = 0; i < k; i++) {

p1 = p1.next;

}// 注意这里是向后处理k次

ListNode p2 = head;

// p1 和 p2 同时走 n - k 步

while (p1 != null) {

p2 = p2.next;

p1 = p1.next;

}

// p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点

return p2;

}

2. 在这个真题的处理上，建立了虚拟结点来处理边界问题

   为了防止出现空指针的情况，比如说链表总共有 5 个节点，题目就让你删除倒数第 5 个节点，也就是第一个节点，那按照算法逻辑，应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了，这就会出错。但有了我们虚拟节点 dummy 的存在，就避免了这个问题，能够对这种情况进行正确的删除。

26. 删除有序数组中的重复项(8.14)

1. 双指针技巧：用于在链表或数组中原地索引或修改，这类过程一般需要数组中元素自身作比较，使用双指针（可以是不同步移动、同步移动）

   左右指针是两个指针相向而行或者相背而行；快慢指针是两个指针同向而行，一快一慢。

   对于单链表来说，大部分技巧都属于快慢指针，因为无法直接定位到链表的末尾。单链表的六大解题套路 都涵盖了，比如链表环判断，倒数第 K 个链表节点等问题，它们都是通过一个 fast 快指针和一个 slow 慢指针配合完成任务。

2. 【原地修改】：

   如果不是原地修改的话，直接new int[]，把去重之后的元素放进这个新数组中，然后返回这个新数组即可。但是原地删除，不允许new新数组，只能在原数组上操作，然后返回一个长度，这样就可以通过返回的长度和原始数组得到我们去重后的元素有哪些了。

   所以该题无所谓去重后剩余空间中的数字，无需考虑剩余空间的处理。

   3.采用快慢指针策略：让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。这样，就保证了 nums[0..slow] 都是无重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是整个数组去重之后的结果。

<code>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[0..slow] 无重复

nums[slow] = nums[fast];

}

fast++;

}

// 数组长度为索引 + 1

return slow + 1;

}

}

27.移除元素(8.16）

1. 这道题和上一道思路很像，通过fast指针遍历后移来扫描元素，在满足条件时替换(赋值)slow指针，本质上是删除重复/不需要的元素，同时缩短整个数组

   把nums中所有值为val的元素原地删除，依然需要使用快慢指针技巧：

   如果 fast 遇到值为 val 的元素，则直接跳过，否则就赋值给 slow 指针，并让 slow 前进一步