算法（数组+链表）

37.移除元素

数组的删除其实是元素的覆盖比如刚开始五个元素删除了一个他变成了四个元素但是他的空间大小还是五

删除元素是o（n）erase的时间复杂度是o（n）

暴力实现

当使用两层for循环去删除元素的时候

比如要删除元素三但第一个for循环到数字三的时候在第二个for循环中进行覆盖

双指针的实现

使用一层for循环解决

首先先定义一个快指针一个慢指针快指针是指向新数组所需要的元素需要更新的下标就是我们的慢指针我们将快指针的值赋给慢指针

新数组是获取要更新的元素慢指针是获取我们新数组中需要更新的位置

for循环中的if操作其实就是一个更新的操作如果快指针等于val目标值就不进行if 只有不相等的时候才进if 慢指针才++ 最后慢指针指向的是新数组的大小

977有序数组的平方

有序数组的话他如果有负数的话是左右两边的平方大于中间的数所以可以使用左右的双指针来往中间走

首先先定义一个数组定义一个k=size-1也就相当于最后一个的下标值

将i放在左边 j放在右边

然后进行比较将平方的最大值放到k的位置然后k-- 途中可以简化代码直接写k--

如果是i就向右++j的话就向左--

209长度最小的子数组

暴力思想

两层for循环

滑动窗口

我们使用滑动窗口的思想去解决

其实和双指针的思路差不多只不过是我们取的是双指针中间的那块就像一个滑动窗口

使用了一个for循环做了两个for循环做的事情

首先我们先思考一下for循环中的j 是起始位置的j还是终止位置的j

首先如果他是起始位置的j的话终止位置慢慢向右移动最后得到数组看是否满足题目大小这个其实和两个for循环的暴力思想差不多

所以这边的 j是终止位置的起始位置的话需要我们去利用一个动态移动去移动起始位置（精华）

for循环中的j已经确定了是终止位置

起始位置的寻找：当我们一步一步向右移动终止位置的时候当找到集合中的大小大于等于s的时候开始移动起始位置这样就可以动态的收集不同区间里面的和

题目讲解

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/minimum-size-subarray-sum/solutions/305704/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio

59螺旋矩阵

在螺旋矩阵的时候四个角的边界点不容易处理

我们要遵循一个循环不变量就是对每条边处理的一个规则是左闭右开还是什么这个规则左闭右开就是只处理第一个节点最后一个节点留给下一条边

还有就是他可以转几圈的问题一般是n/2 如果n是奇数的话怎么办当n为奇数的话都会留下中间的那个位置我们只需要判断一下 n如果是奇数我们对我们所填充的这个数组叫做numbers作为单独的数组把最后的值赋给他就可以了

解决了转几圈我们进入循环我们要定义好起始位置 startx=0 starty=0 在定义一下offect=1 count=1

代码实现

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/spiral-matrix-ii/solutions/12594/spiral-matrix-ii-mo-ni-fa-she-ding-bian-jie-qing-x

203移除链表元素

头节点和中间节点的删除方式不一样

中间的节点需要要前面的节点指向下一个节点

但是我们如果引入一个虚拟的头节点所有节点的删除方式就一样了

方法一（不引入虚拟）

判断头节点是否为为空同时头指针指向的数值等于我们的target

这样的话只需要让head=head->next

需要注意的一点就是

这种情况当把头节点删除的时候他的下一个还是头节点所以需要在上面的代码上加上while

头节点处理完之后剩下的就是非头节点 定义一个cur指向head第一个节点 假如第二个节点是需要删除的元素只需要让cur指向cur的next的next就行同时把cur的next删除

同时要判断cur不能为空和cur的next也不能为空因为cur要指向下一个元素为空的话会报空指针异常 cur的next要和target进行作比较如果他的next为空又是操作空指针

方法二（虚拟头节点）

new一个dummy head让dummy head指向head

定义一个cur去遍历链表用cur=dummy head 如果cur的next不为空的话就用while去循环

然后cur的next=cur的next的next

如果没有找到我们的target cur就继续往下遍历使用虚拟头节点的话 我们要return的就是dummy的next才是新链表的头节点

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/remove-linked-list-elements/solutions/813358/yi-chu-lian-biao-yuan-su-by-leetcode-sol-654m

707设计链表

获取第n个节点的值

我们可以加入虚拟头节点方便我们的增删查改

首先我们获取第n个节点的值这个的话我们需要去判断n n如果小于0或者n>size-z则不满足条件

我们先定义一个cur用来遍历链表让他直接指向dummy head的next 这边的话要注意以下边界的问题比如cur的下一个指针为空的话我们要直接返回当前的cur 否则会出现空指针异常

头部插入节点

首先 new一个新的节点因为我们引入了虚拟的头节点只需要讲new的节点放到两个节点之中就ok

这边有一个小坑就是在插入的顺序问题中我们首先new出了新的节点然后将dummy head 的next指向newnode 但是这边当这个操作之后第三个节点就找不到了因为之前dummy head 的next就是他现在反而娶不到了

那么正确的顺序是先new node 的next=dummy head 的next这样就可以获取到第三个节点然后再让dummy head 的next指向new node

在尾部插入节点

我们先定义一个新的节点让cur=dummyhead

要让cur停到最后一个节点他的循环条件就是 cur的next=null

第n个节点前插入节点

先定义一个cur让他等于dummy head 寻找第n个节点

这边直接将n放到了while循环中并n-- 我们取一个极端的情况就是当n为0的时候不进入循环

那直接返回的就是dummy head的next 也就是第0个节点之前

我们要先new node的next指向cur的next再让cur的next=new node

删除第n个节点

cur=dummy head

要删除的第n个节点也就是cur 的next 可以假设n为0 并且只有一个节点那么不进入循环删除的就是

cur的next也就是第一个节点

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/design-linked-list/solutions/1840997/she-ji-lian-biao-by-leetcode-solution-abix

206反转列表|双指针法|递归法

这道题我们可以使用双指针或者递归的解法

双指针

定义两个指针一个是cur一个是pre

大体的过程就是将 cur指向pre

首先初始化的话就是cur=head pre=null

遍历的过程 什么时候算遍历结束

当我们的cur指向了空指针的时候我们的pre指向的是尾节点这个遍历的操作就结束了

我们让cur指向了pre 但是我们怎么才能获取到 cur 的下一个节点这里的话我们就需要一个temp来进行一个暂存没赋值之前我们先将cur的next赋值给temp

然后cur=temp 最后新列表的头节点就是pre

递归

首先先有reverse 的函数两个参数分别是cur 和pre 在主函数中调用reverse

主函数中给reverse 的两个参数就分别是head 和null

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/reverse-linked-list/solutions/551596/fan-zhuan-lian-biao-by-leetcode-solution-d1k2

24两两交换链表中的节点

思路

我们还是使用虚拟头节点的操作

在进行交换的时候需要先将dummyhead节点指向2节点指向1节点指向三节点

这里经常犯空指针异常或者是无限循环的错误

先定义一个虚拟头节点dummy head 指向head

cur指针先指向dummy head

这边的话链表中的节点可能有奇数个也可能有偶数个奇数个的话剩余最后一个就不做交换了偶数的话正常进行一个交换

奇数情况下 cur 的next的next为null则结束

偶数情况下cur 的next为null则结束

代码书写的时候这里要先写保证cur的next不能为空再写cur的next的next不能为空如果写反的话可能先判断cur的next已经为空了又进行了一个next 则空指针异常 所以这边的顺序是一个坑把这两个条件放到while循环中

cur的next的next赋值给cur的next 但是节点一的指针已经断了所以要在之前先把cur的next赋值给temp temp1=cur的next的next的next

之后再把temp赋值给cur的next的next

temp1赋值给temp的next

紧接着需要去移动cur 直接往后移动两位就是cur的next的next

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/swap-nodes-in-pairs/solutions/444474/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-91