快慢指针的在leetcode的问题中有很多应用，例如通过一次遍历找到链表的中间节点。 这里要介绍的是作为哨兵，应用于数组或者链表中删除特定元素，不另外开辟空间，即空间复杂度为O(1)
删除有序数组中的重复项
在这里插入图片描述
在这里插入图片描述
因为是有序数组，所以重复的元素都是在一起的。暴力处理，每次判断当前元素和后一个元素是否相同，不相同则删除，而删除需要移动后面的元素，时间复杂度为
O(n^2)
使用快慢指针，slow记录的是不同元素的索引。fast作为哨兵，一开始指向slow的下一个元素，如果遇到不同的元素则赋值给slow， 最后返回数组的长度为slow + 1（索引从0开始，长度需要+1）。 此时数组中的前 slow + 1个元素都有不同的值。
代码如下：
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
slow = 0
nums_len = len(nums)
for fast in range(1,nums_len):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
时间复杂度为：O(n)
空间复杂第为： O(1)
删除排序链表中的重复元素
在这里插入图片描述
在这里插入图片描述
方法和上一题一样，这里需要注意，链表需要将slow的下一个节点置为None
代码如下：
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head:
return None
slow,fast = head,head
while fast.next:
fast = fast.next
if fast.val != slow.val:
slow = slow.next
slow.val = fast.val
slow.next = None
return head
时间复杂度为：O(n)
空间复杂第为： O(1)
移除特定元素
在这里插入图片描述
在这里插入图片描述
同样利用使用快慢指针。
slow初始值为-1，不指向任何元素，因为有可能整个数组都是待删除的元素。fast作为哨兵，从头遍历。如果遇到不等于val的元素则赋值给slow， 最后返回数组的长度为slow + 1。
代码如下：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
if len(nums) == 0:
return 0
nums_len = len(nums)
slow = -1 #
for fast in range(nums_len):
if nums[fast] != val:
slow += 1
nums[slow] = nums[fast]
return slow + 1
时间复杂度为：O(n)
空间复杂第为： O(1)
移动零
在这里插入图片描述
思路于上面一个问题一样，只不过这里不是移除元素0，而是要将元素0移至末尾，因此这里要进行元素的交换，而不是直接赋值
代码如下：
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if len(nums)==0:
return
slow = -1
nums_len = len(nums)
for fast in range(nums_len):
if nums[fast] != 0:
slow += 1
# 进行元素的交换，而不是直接赋值
tmp = nums[slow]
nums[slow] = nums[fast]
nums[fast] = tmp
时间复杂度为：O(n)
空间复杂第为： O(1)
