链表

以下内容仅为刷题总结，只记录目前遇到过的情况，如果后面遇到了更多可能性再总结

链表定义

在链式存储当中，对于节点是使用指针指向的方式进行数据的存储，其结点定义类似如下形式：

struct LinkNode {
    int val;
    LinkNode *next;
    LinkNode() {}
    LinkNode(int x) : val(x), next(NULL) {}
};

链表的好处是在添加或者删除特定节点的时候时间复杂度比顺序存储要小。在经常需要删除和添加操作节点的时候，通过直接修改节点的指针，可以快捷的对节点进行对应操作。

结构

链表划分为三个部分，头+中间的数据节点+尾。

头结点

其中头节点有两种常见的处理方式，一种是通过一个虚拟的dummyhead来当作头结点，之后才是真实的数据节点。这样的好处是可以在对实际含有意义的头节点进行操作的时候，不需要有额外的特判就可以完成，通过增加一个头结点在部分题目中有的时候可以有很好的效果。

尾节点

尾节点和头结点一样，也有实际意义上存在的数据节点和最后指向的一个尾巴节点，不过根据节点的定义来看，可以知道尾节点后面通常都跟有一个无意义的nullptr。在有的时候需要对尾节点进行处理的时候，增加一个虚拟的dummytail也许也能起到很好的效果。(p.s. 比如在写双向链表的时候)

指针

创建链表的时候，通常会创建一个指针节点来表示整个链表的头节点。

LinkNode *ListA = new LinkNode();

以上代码的含义即为创建一个LinkNode的节点，同时创建一个叫做List

A的指针，指向的是这个节点的内存。

而在对单向链表的进行操作的时候，如果我们移动了链头，很多时候意味着操作都是不可逆的。因此如果需要对链表中某个特定节点进行操作的时候，往往都会创建一个指向需要节点的指针来进行单独操作，操作完毕后将指针释放即可。

以下举例，阐明节点和节点指针之间的关系：(感觉有点废话)

LinkNode *cur = new LinkNode();  // 创建一个cur指针
LinkNode *A = new LinkNode(114);  // 创建节点A
LinkNode *B = new LinkNode(115);  // 创建节点B
cout<<"cur addr:"<<cur<<" "<<"A addr:"<<A<<" "<<"B addr:"<<B<<endl;
// 此时cur、A和B表示的内存地址
cur = A;
LinkNode *tmp = A;
cout<<tmp<<endl;
// 让cur指向A之后cur的内存地址
A = B;  // 让A指向B
// delete tmp;  // 是否删除原本A代表的节点对应内存
cout<<"cur addr:"<<cur<<" "<<"A addr:"<<A<<" "<<"B addr:"<<B<<endl;
cout<<cur->val<<endl;
return 0;

在注释了delete tmp的时候，最后输出的cur->val会依旧是114这个A曾经的值，而如果执行了对应的delete操作，由于原本A对应内存上的结构体被释放了，所以这个时候cur就没有指向一个有效的节点。

算法题

链表的终止条件

常用的终止条件有三种：

1. cur != nullptr 指针会停留在nullptr的尾节点上
2. cur->next != nullptr 指针会停留在最后一个有效节点上
3. cur != nullptr && cur->next != nullptr多用于快慢指针，用于判断快指针是否到队尾。之所以两种情况都判断为循环跳出的条件原因：由于nullptr本身相当于最后一个有效节点的附加尾巴。类比于线段上有区间(a, b)和区间[a,b]，快指针的目的是为了判断长度，而这两种区间长度都是b - a，只是对于第一种情况(a, b)如果不将b节点本身纳入有效节点则会出现区间长度变为a -> (b - 1)的情况。

对于第三种终止条件，还可以类比为：

• cur == nullptr终止的情况就是区间(a, b)，此时cur在走到b的时候快指针已经越界，刚好碰壁
• cur->next == nullptr终止的情况就是区间[a, b]，此时cur在走到b时，刚好到达边界，也同样碰壁。