代码随想录算法训练营第三天

题目：Leetcode 203 移除链表元素

从今天开始进入链表的学习

        思路：

        Leetcode中给出的链表头结点并不是书上写的不存元素的虚拟头结点，而是书上所说的首元结点。也就是head就是链表的第一个结点。

        这个题目有两种解题方法：

                第一种：直接在原数组上操作。                      

1. 定义两个指针 p 和 q，其中 p 指向当前节点，q 用于辅助删除节点。
2. 遍历链表，直到遍历到链表的末尾或者 p 的下一个节点为空。
3. 在遍历过程中，判断 p 的下一个节点的值是否等于给定的 val。
   • 如果相等，说明需要删除该节点，将 q 指向该节点，然后将 p 的下一个指针指向 q 的下一个节点，即跳过了节点 q。
   • 如果不相等，说明节点值不是要删除的值，将 p 移动到下一个节点。
4. 循环结束后，如果头节点 head 的值等于给定的 val，则将头节点指向下一个节点，即删除头节点。
5. 返回修改后的链表头节点

              第二种：虚拟头结点操作

        细节点：当一个指针不用时，记得要释放空间，虽然不报错。

                思路挺简单的，不说了。

题目：Leetcode 206 反转链表

 思路：反转链表同样用虚拟头结点的方法，但是并不是真正创建了一个结点，而是一个空指针pre，分为递归和双指针两种方法。

                双指针法：当cur指针不为NULL时，用temp记录下当前指针的下一位，此时我们有了三个指针。先把当前指针cur指向pre，再把这两个指针向后移动一位，继续以上操作，直到cur == NULL，即cur指针到达链表最后一位的后一位，此时pre指针在最后一位，返回pre。因为cur代表的本来就是头结点了，并不是虚拟结点的下一位

                递归法：递归法和双指针法主体上类似，只是每次直接就传了temp和cur指针，不需要pre和cur向后移动

题目：Leetcode 707 设计链表

这个题目有点难，还没搞清楚 

这篇好文章是转载于：学新通技术网