1、线性表的链接存储结构
1、线性表的链式存储结构——链表
（1）如果每个节点只设置一个指向其后继节点的指针成员，这样的链表称为线性单向链表，简称单向链表。
(2)如果在每个节点中设置两个指针成员，分别指向其前驱节点和后继节点，这样的链表称为线性双向链表，简称双向链表。
2. 单链表
每个节点都是一个类对象，包括存储元素的数据列表data和存储后续节点的指针属性next。
单链表类
节点引用方法：
插入节点操作：在单链表中的节点p之后插入节点s。
删除节点操作：删除单链表中p节点的后继节点。
创建一个整体的单链表
从包含 n 个元素的数组 a 创建一个单链表。
创建单链表有两种常用的方法：头插入和尾插入。
使用表头插入方法创建表
从空列表开始，依次读取数组 a 中的元素。
生成一个新的节点s，并将读取到的数据存储到新节点的data成员中。
将新节点s插入到当前链表的头部。
通过头插值方法创建的单链表中数据节点的顺序与a数组中的顺序正好相反。
使用尾插法建表
从空列表开始，依次读取数组 a 中的元素。
生成一个新的节点s，并将读取到的数据存储到新节点的data成员中。
将新节点s插入到当前链表的末尾。
通过头插值方法创建的单链表中数据节点的顺序与a数组中的顺序完全相同。
3、单链表中线性表基本操作的实现
查找序号为i的节点（0≤i≤n-1，n为单链表中数据节点的数量）
Add(e) 到添加元素 e 的线性列表的末尾
求线性表的长度()
查找线性表中序号为i的元素(i)
设置线性表中序号为i的元素(i,e)
查找线性表中第一个值为e的元素的逻辑序号 GetNo(e)
插入 e 作为线性列表中的第 i 个元素 (i, e)
删除线性表中的第 i 个数据元素 (i)
删除第i个节点的算法
输出线性表的所有元素()
4. 基于单链表基本操作的算法设计
练习1：有一个长度大于2的整数的单链表L。设计一个算法来查找L中中间位置的元素。
例如L=(1,2,3)，返回元素为2； L=(1,2,3,4)，返回元素为2。
计数方法：计算L的长度n。假设第一个节点的个数为1，则满足题目要求的节点个数为(n-1)/2+1（这里的除法是整数除法）。 设j=1，指针p指向第一个节点，并将其向后移动(n-1)/2-1个节点。
快慢指针法：先设置快慢指针指向第一个节点。 当快节点后面至少有两个节点时，让慢指针每次移动一个节点，让快指针每次都变快。 移动两个节点。 否则，slow指向的节点就是满足问题要求的节点。
练习2：有一个整数的单链表L，其中可能有多个具有相同值的节点。 设计一个算法来查找 L 中具有最大值的节点数。
解决方案：首先让p指向第一个节点，用maxe记录第一个节点的值，将其视为最大节点，并将cnt设置为1。循环如下，直到p指向尾节点：
(1) 如果p.next.data>maxe，则将p.next作为新的最大值节点，设置maxe=p.next.data，cnt=1。
(2) 如果p.next.data==maxe，maxe仍然是最大节点值，设置cnt++。
(3) p 向后移动一个节点。
最后返回cnt，即最大节点数。
练习3：有一个整数的单链表L，其中可能有多个具有相同值的节点。 设计一个算法来删除L中具有最大值的所有节点。
解决方法：流程如下：
首先遍历L的所有节点，找到最大节点值maxe。
再次遍历删除所有值为maxe的节点。 删除时，通过一对(pre,p)指针指向两个相邻节点。 如果p.data==maxe，则通过pre节点删除p节点。 观点。
练习 4：有一个整数的单链表 L。 设计一个算法，将L中所有节点求逆。例如，L=(1,2,3,4,5)，求逆后L=(5,4,3,2,1)。
练习 5：有一个包含 2n 个整数的单向链表 L = (a0, b0, a1, b1,..., an-1, bn-1)。 设计一个算法，将其拆分为两个带有前导节点的单链表 A。 和B。
其中 A=(a0,a1,…,an-1), B=(bn-1,bn-2,…,b0)。
练习6 有两个递增有序整数单链表A和B。设计算法，使用双向合并方法将A和B的所有数据节点合并到递增有序单链表C中。
所需算法的空间复杂度为O(1)。
练习7 有两个递增排序的整数单链表A和B。假设每个单链表中没有具有相同值的节点，但两个单链表中存在具有相同值的节点。 设计一个尽可能高效的算法，构建一个新的增量有序整数单链表C，其中包含A和B值相同的节点。要求算法执行后，单链表A和B不会改变。
该算法的时间复杂度为O(n+m)。
空间复杂度为 O(MIN(n,m))。
其中，m和n分别是单链表A和B中数据节点的数量，MIN是最小值函数，因为单链表C中最多有MIN(n,m)个节点。
