链表理论基础

链表是通过指针串联在一起的线性结构。

链表中的每个结点可以分为两个部分：数据域和指针域。数据域用于存储该结点存储的数据。指针域用于记录下一个结点的指针，若指针域为null，则表明该结点是链表中的最后一个结点。

链表的入口结点也就是链表的第一个结点，被称为头结点。

链表的分类可以分为：单链表、双链表和循环链表。

单链表：结点中仅包含一个指针，且该指针指向链表中的下一个结点，这种链表就被称为单链表。

双链表：每个结点中包含两个指针，一个指针指向下一个结点，一个指针指向上一个结点。则由包含两个指针的结点组成的链表被称为双链表。单链表只能向后查询，不能向前查询。但是双链表既可以向后查询也可以向前查询。

循环链表：循环链表指链表中最后一个结点的指针不为null，而是指向第一个结点的链表，这种链表首尾相连。可以解决约瑟夫环问题。

链表的存储方式：数组的存储方式是在内存中申请了一片连续的存储空间，可以通过下标快速访问数组中的每个元素。而链表在内存中不是连续分布的，而是可能零散的分布于内存中。但为了确保链表中的数据的顺序，可以通过结点的指针域确定下一个结点的位置。从而将零散的分布在内存中的结点通过指针串联起来，从而形成顺序。

自定义链表节点：

struct ListNode {

int val; // 节点上存储的元素

ListNode *next; // 指向下一个节点的指针

ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数

};其中，ListNode(int x) : val(x), next(NULL) {}是定义链表结点的构造函数，将参数处的数据放入数据域，同时让指针域为空。在写自定义链表结点的时候，可以不写结点的构造函数，但是没有办法在初始化结点的时候为其数据与赋值，只能在之后通过手动方式为其赋值。

链表的操作：在链表中删除或添加结点的时候，可以避免像数组一样对其他元素进行大量的移动操作。删除结点时，只用将被删除结点的前一个结点的指针域指向被删除结点的下一个结点即可。添加结点亦然，新添加的元素的指针域指向插入位置的下一个结点，且前一个结点指向新插入结点即可。需要注意：删除结点时最好将被删除的结点内存释放掉，这样才是真正删除了结点；而之前只是从逻辑上在链表中删除了该结点。链表的添加和删除的时间复杂度都是O(1)。但是链表在查询指定位置的结点时只能通过遍历的方式进行，时间复杂度为O(n)。

数组和链表的区别：数组的长度固定，而链表的长度可变。

今日练习：

203移除链表元素√

这道题很简单，首先需要确保头节点中保存的值不是要被移除的值，如果头节点的值为要移除的值，则让头节点后移，直至找到一个有效的值作为链表的头节点。

之后创建一个用于遍历的，表示当前检查位置结点的前一个结点的结点，其起始指向头节点。并判断该结点的下一个结点的值是不是要移除的值，这么做的主要原因是，由于这是个单链表，只能用要判断结点的前一个结点进行判断，如果直接用当前结点进行判断，当发现当前结点存储的值是要移除的值时，无法找到其前一个结点。之后逐个向后遍历即可。

707设计链表√

本题有两个要注意的点：

1.创建头节点，每次遍历都可以从头节点开始，这样会方便很多，也更容易思考。

2.注意边界。第一次提交的时候前60个测试用例时正确的，但是后边每个测试用例都出现了边界问题，要插入的位置或者要删除的位置其实不存在，但是我在写的时候并没有考虑到。

206反转链表√

这应该是今天最简单的一道，第一次遍历找到最后一个结点，并记作trail。之后再从头遍历一次，将每个结点都插到trail的后一个即可。时间复杂度应该为O（n）