链表理论基础

数据结构视频里面看过讲解，代码看过逻辑，但是没有具体实现过。

链表包括：单链表（单方向）、双链表（向前查询和向后查询）和 循环链表（首尾相接）。

链表在内存中不是连续的。

C++定义链表的方式：

链表删除节点时记得释放。链表增添和删除都是O(1)操作，但是查找的时间复杂度是O(n)。

203.移除链表元素

思考过程：很简单的查找，删除过程，但是链表的删除有注意点，先传地址再free

从来没写过链表题，直接看代码随想录：

我少思考了：如果对应元素在链表头怎么办，在链表尾怎么办

链表头：

1）直接用原来的链表进行删除操作（头结点向后挪一位就可以，free掉原来的头结点）（这道题是单链表）

好处：简单；

坏处：需要单独针对头结点写代码。

 2）设置虚拟头结点进行删除操作

好处：所有链表元素的删除都可以按照同一段代码完成

链表尾：最后指向null

707.设计链表

思考过程：

这道题其实是上一道的进阶版，不仅需要写删除，还需要写查找和增加。不过好处是，写了查找之后，就可以在每个函数中直接调用，不需要增加和删除都写查找了。

看代码随想录：

对于插入链表元素来说，使用虚拟头结点的代码简便且插入简便。

206.反转链表

思考过程：

链表必须要从开头开始传递。首先设置虚拟头结点，将原先头结点next传递到cur->next中，一步一步将指向变换就可以。

代码随想录：

和我的思路是一样的，但是我不会具体实现。

双指针的方法这里也可以用！算是快慢指针8

总结：

虽然学完了数据结构，但是链表的代码从来没有自己写过，只是在脑子里面大概知道是什么样的步骤该怎么做。

这三道题都是比较基础的链表功能基本实现的问题，这次都是直接看的卡哥答案照着敲的，要多敲几次熟练一下。