双指针

1 数组-移除元素

题目：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

思路：

快指针f慢指针s，当检测到需要删除的元素时，s停止一步，f前进一步，且将s下标赋值为f，做逻辑删除，最后resize到s下标大小即可

2 字符串-反转字符串Ⅱ

题目：

反转字符串

思路：

for循环，双指针，一个指向头，一个指向尾，做swap，停止条件为左指针大于右指针

3 字符串-替换空格

题目：

替换字符串s中的空格为指定字符串j

思路：

第一个for循环，检测字符串中的空格数量，然后resize字符串，扩充至需要的长度，第二个for循环，双指针，快指针指向resize后的字符串末尾，慢指针指向old指针的字符串末尾，当慢指针检测到空格时，反向赋值j，终止条件为指针=0

4 字符串-翻转字符串里的单词

题目：

给定一个字符串，逐个翻转字符串中的每个单词。

思路：

首先去除多余空格，然后先将整个字符串翻转，在for循环，双指针，快慢指针初始值都为0，快指针++，检测到空格时就反转快慢指针之间的部分字符，注意最后快指针到末尾时再反转最后一个单词。

5 链表-反转链表

题目：

题意：反转一个单链表。

思路：

快慢指针，挨个反转，注意定义tmp指针进行保存下一个节点即可

6 链表-删除链表的倒数第N个节点

题目：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

要求：使用一趟扫描实现

思路：

快慢指针，快指针比慢指针快n，当快指针走到最后一个结点时，删除慢指针指向节点即可实现一个循环删除

7 链表-链表相交

题目：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

思路：

如果相交说明在某一个节点之后两个单链表完全相同，将较长的链表定位到倒数较短链表长度位置，判断是否相同(注意不只是val值相等)，相同则相交了

8 链表-环形链表Ⅱ

题目：

题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

思路：

快指针每次走两步，慢指针每次走一步，当快指针追上慢指针就说明有环，当相遇时，重新设置两个指针，一个指向头节点，一个指向相遇的节点，两个节点相遇的节点就是入环的第一个节点

8 哈希表-三数之和

题目：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

思路：

先sort冒泡排序将nums转换为有序数组，for循环，i从0开始，左指针从i开始，右指针从nums.size()-1开始，令i,左指针，右指针下标数字为num_i,num_l,num_r。当num_i+num_l+num_r小于0，则左指针右移；若大于0，则右指针左移；若=0，则保存一个三元组，并且左指针右移，右指针左移，此时还要执行剪枝1。

• 剪枝1：若num_l或者num_r相邻值相等，continue，
• 剪枝2：若num_i大于0，break，return保存的三元组
• 剪枝3：num_i若和num_(i-1)相同则continue，这样处理是因为可以有i和left相等的情况。

8 哈希表-四数之和

题目：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c，d ，使得 a + b + c + d = 0 ？请你找出所有满足条件且不重复的三元组。

思路：

在三数之和的基础上多一个for循环，即i，j，left，right，此时剪枝需要稍作改变，

• 剪枝1：若num_l或者num_r相邻值相等，continue，

• 剪枝2：若num_i大于0，break，return保存的三元组

• 剪枝3：i>1且num_i若和num_(i-1)相同则continue，这样处理是因为可以有i和left相等的情况。

• 剪枝4：j>i+1且num_j若和num_(j-1)相同则continue，这样处理是因为可以有i和left相等的情况。

• 剪枝5：i>=j时continue