算法练习day3

移除链表元素

代码随想录 移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

（用时：0.5小时）

普通方法

普通的移除方法中，要将节点分为头结点和非头结点两类。

• 如果头结点就是要移除的元素，那么直接让其next成为头节点即可（即缩头）

• 如果是非头节点，让节点的前一节点的next指向要移除的节点的next即可。

错误

自己也没有想到，普通写的时候还出了好些问题，果然是不熟练啊。

错误：头节点不能用if，也要用while来筛除。 如果用if，那就只判断了一次头节点，那万一头节点的下一个头节点也是要删的呢？（也不知是不是unity的update写多了，写函数的时候脑子里一直是if也会循环hhh）

虚拟头结点法

虚拟头结点就是在原来的头结点前，增加一个头结点，让这个头结点暂时充当头结点。这样就消除头结点的特殊情况，少if判断。

既然消除了头结点的特殊情况，题目也就变成了

重点分析

重点有以下三个：

1. while中的判断条件？

2. if判断的判断条件？

3. if判断成立与否时，要做的操作、分别表示什么？

4. currentNode的初始值？

个人的理解如下：

• if的判断

  先考虑if的判断条件是因为while的判断条件要根据if的逻辑来写。 当currentNodex.val等于要找的val移除当前节点，让需移除节点的前驱节点的next等于其下一节点（即frontNode.next = currentNode.next）。
  注意，这里是知道需移除节点的前驱节点的，而这里用的又是单向链表，那就只有“未雨绸缪”，在它的前驱节点时就判断它是否要被移除，要的话让前驱节点实施才行。 不等于时，继续遍历。

• currentNode的初始值

  currentNode的初始值就很简单了，根据前面这里的if判断，初始值应该是虚拟节点。

• while中的判断条件？

  所有的节点都是一类了，那么就只有这一个while了。while里的条件必定是让currentNodex停下来不继续遍历的。问题在于是currentNode还是currentNodex.next不等于null。
  单独看while，这里两者好像都可以。但是我们得配合里面的if。if判断的是currentNode.next的值是否为0，这个currentNode.next必须要是非null，.val才能引用，不然会报错。所以条件是currentNode.next!=null。

设计链表

代码随想录 设计链表

707. 设计链表 - 力扣（LeetCode）

（用时：1.5小时）

思路分析

这道题是设计类的题目。设计“类”的话，方法和思路就很多了。所以写的时候就老是在优化，觉得这里能写的更好，然后就写了好久。。。（怎么有点职业病的感觉hhh）

这道题就是对链表的增删查改。增删改都要在查的基础上，但是题目需要实现的函数只是给定下标，返回值就好，这在数组的增删改上挺好的（数组的查也就是下标引用hhhh），但在链表上，就有点鸡肋了。于是最开始先写了个查的函数，给定下标，返回指向该节点的指针（不知道会不会有什么内存方面的浪费？以往写类都不是为了不是很注重算法的东西，写的又不是c++，对这方面不是很敏感）

删和改的函数没什么好说的，主要就是利用这个查的函数。

增的函数，可考虑的就多了。总所周知链表的插入有头插和尾插两种。刚开始写的时候没有想到虚拟头节点的运用，就用头插和尾插的角度进行了分析。后来进行了迭代，增加了虚拟头结点，不分什么头插尾插了。

• 01：定义三个函数。（如果没有虚拟节点，那么最简洁方便的就是这样）
  第一个，查找节点函数。给定index，返回指向第index个节点的指针。
  第二个，头插法函数。给定index，在该index前面插入新节点

  

  第三个，尾插法函数。给定index，在该index后面插入新节点。

  

  插入节点分为三种情况：
  1.增加头结点：在原来的头结点上用头插法；
  2.增加尾节点：在原来的尾节点上用尾插法；
  3.中间的节点：自主选择是在第index个节点上用头插还是尾插）

• 02：定义两个函数。这里省略了头插法的函数，因为有了虚拟节点。
  第一个，同上
  第二个，尾插法函数。同上

  有了虚拟头结点，插入节点的三种情况的思路稍微改变了：
  1.增加头结点：在虚拟头结点处用尾插法；
  2.增加尾节点：在原来的尾节点上用尾插法；
  ​​​​​​​3.中间的节点：自主选择。若在index前面插入，则在index-1上用尾插法。若在index后面插入，则在index上用尾插法）

反转链表

代码随想录 反转链表

206. 反转链表 - 力扣（LeetCode）

（用时：0.5小时）

双指针法

单向链表的节点的前驱节点自己是不知道的，因此在遍历和更改的时候，需要定义多个指针，防止断链的情况。画图分析：

随意找中间的某个节点进行翻转，发现至少需要一个cur指针用于向前遍历，front指针记录cur的前驱节点以及一个back指针记录后驱节点防止反转后cur无法进行遍历（看视频的时候，也有说back是临时的，所以不算第三个指针。)

重点分析

这道题有几个需要注意的重点：

1. back指针记录cur后驱节点应在改变cur指针next朝向前进行，不然会cur处断链，cur后续无法继续遍历。

2. front指针的更新应该在cur指针的更新之前，因为此时的front指针的next已经这次循环之前就被改了朝向。

递归法

能够被循环迭代实现的，一般都能写成递归。

这道题由于已经给出了调用函数的定义，因此无法在其基础上改成递归函数。定义一个新的函数，用于处理递归的逻辑。

• 递归的参数：递归函数的参数是要一直改变的值。在循环中，cur和 front的值一直在更新（back是临时的），因此递归的参数就是cur和front。

• 递归的出口：递归函数的出口就是循环终止的条件。在循环中，while的终止条件是cur为null，因此这就是递归的出口。

• 递归要处理的逻辑：递归的逻辑就是循环要做的东西。在循环中，其实是一直重复着临时指针back指向cur后驱节点、改变cur的next朝向和front、cur更新的操作。那在递归了也如此，只是注意front、cur的更新要在给递归函数传参时体现。