线性表复习和进阶学习
大学的时候不好好学习，老师在讲台上讲课，自己在以为老师看不到的座位看小说，现在用到了老师讲的知识，只能自己看书查资料进行再回炉学习，真心对不住老师，对不住父母，对不住自己的青春啊！
有些路，就是需要你自己走，有些知识就是需要你掌握，不论早几年还是现在还是几年后。。。是你的终归还是你的。。。
什么是线性表？
线性表：零个或者多个数据元素的有限序列。
我们可以看出别管上边说的前驱还是后继，都是在表达这个序列是有序的，即：前面有且仅有一个元素，后边有且仅有一个元素（除了首尾两端）。
在较复杂的线性表中，一个数据元素可以由若干个数据项组成的。
我们首先来看这个线性表都包含什么：看下图我们可以看出，线性表里面比较常见的两个结构是：顺序存储结构和链式存储结构，而链式存储结构下边又分为：单链表、静态链表、循环链表、双向链表。
1、顺序存储结构：
我们来看线性表的顺序存储结构的代码
我们可以发现描述顺序存储结构需要的三个属性：
（1）存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
（2）线性表的最大存储容量：数组长度MaxSize。
（3）线性表的当前长度：length。
顺序存储结构的插入和删除
（1）插入
插入的思路：1、如果插入的位置不合理，抛出异常。
2、如果线性表长度大于等于数组长度，则抛出异常或动态增加容量。
3、从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。
4、将要插入的元素填入位置i处。
5、表长加1。
（2）删除
删除的思路：1、如果删除位置不合理，抛出异常。
2、取出删除元素。
3、从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置。
4、表长减1。
顺序存储结构的优缺点
优点：无须为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速的存取表中任一位置的元素。
缺点：插入和删除操作需要移动大量元素；当线性表长度变化较大时，难以确定存储空间的容量；造成存储空间的“碎片”。
问题的暴露：
这样我们就引申出来了线性表的链式存储结构。
为了解决上边暴露出来的问题，我们让相邻的元素之间留有足够的余地，并且所有的元素都不要考虑相邻位置了，只让每个元素知道它下一个元素的位置即可。
我们来看链式存储结构的概念
链表中第一个结点的存储位置叫做头指针。
在单链表的第一个结点附设一个结点叫做头结点。
头指针和头结点的异同：
（1）头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针；
头指针具有标识作用，所以常用头指针冠以链表的名字；
无论链表是否为空，头指针均不为空。头指针是链表的必要元素。
Node** a;
（2）头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义，也可以存放链表的长度；
有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了；
头结点不一定是链表的必须元素。
Node *a;
单链表
我们在C语言中可用结构指针来描述：
我们可以看出：结点是由存放数据元素的数据域和存放后继结点地址的指针域组成。
单链表的插入和删除
（1）插入
单链表第i个数据插入结点的算法思路：
1、声明一个指针p指向链表头结点，初始化j从1开始；
2、当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
3、若到链表末尾p为空，则说明第i个结点不存在；
4、否则查找成功，在系统中生成一个空结点s；
5、将数据元素e赋值给s->data；
6、单链表的插入标准语句：s->next=p->next; p->next=s;
7、返回成功。
红框内是关键代码：
（2）删除
单链表第i个数据删除结点的算法思路：
1、声明一个指针p指向链表头结点，初始化j从1开始；
2、当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
3、若到链表末尾p为空，则说明第i个结点不存在；
4、否则查找成功，将欲删除的结点p->next赋值给q；
5、单链表的删除标准语句p->next=q->next；
6、将q结点中的数据赋值给e，作为返回；
7、释放q结点；
8、返回成功。
红框内是关键代码：
对于插入和删除数据越频繁的操作，单链表的效率优势就越是明显。
单链表结构与顺序存储结构有缺点
（1）存储分配方式：
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素；
单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。
（2）时间性能
查找：顺序存储结构O(1);
单链表O(n)。
插入与删除：顺序存储结构需要平均移动表长一半的元素，时间为O(n);
单链表在找出某位置的指针后，插入和删除时间仅为O(1)。
（3）空间性能：顺序存储结构需要欲分配存储空间，分大了浪费，分小了容易发生上溢；
单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。
经验性总结：
1、如果线性表需要频繁的查找，很少进行插入和删除的操作时，宜采用顺序存储结构。如果需要频繁的插入和删除时，宜采用单链表结构。
2、当线性表中的元素个数变化比较大或者根本不知道有多大的时候，最好用单链表结构，这样可以不用考虑存储空间的大小问题。如果事先知道线性表的大致长度，用顺序存储结构效率要高很多。
静态链表
对于有指针的语言里面，可以利用指针能力，使得非常容易的操作内存中的地址和数据，但是对于没有指针的语言，比如Basic、Fortran等早期的变成高级语言，怎么办呢？
有人想出用数组代替指针！
我们让数组的元素都是由两个数据域组成，data和cur。即数组的每一个下标都对应一个data和一个cur。数据域data，用来存放数据。cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。我们把cur叫做游标。
另外我们对数组的第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把违背使用的数组元素成为备用链表。而数组的第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下表；而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点的作用，当整个链表为空时，则为O²。
静态链表的插入：
静态链表的删除：
静态链表的优缺点：
优点：在插入和删除操作的时候，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除需要移动大量元素的缺点。
缺点：没有解决连续存储分配带来的表长难以确定的问题；失去了顺序存储结构随机存取的特性。
总的来说，静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。
循环链表
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表。简称循环链表。
双向链表
在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以，在双向链表中有两个指针域，一个指向后继，一个指向前驱。
双向链表的插入：
双向链表的删除：
最后加上free（p）释放结点
链表的进阶学习
面试官喜欢考察与链表相关的知识的原因有如下几点：
1、链表的操作代码量比较小，可以在面试的短时间内完成手写代码；
2、链表是一种动态的数据结构，其操作需要指针进行操作，可以检验面试者的编程功底；
3、链表的数据结构很灵活，可以用链表设计具有挑战性的面试题。
我们说链表是一种动态的数据结构，是因为创建链表的时候，无须知道链表的长度，当插入一个结点的时候，我们只需要为新的结点分配内存，然后调整指针的指向被链接到链表中即可。内存分配不是在创建链表的时候一次性完成的，而是每添加一个结点分配一次内存，由于没有闲置的内存，链表的空间效率比数组的要高。
下边我们就几道常见的链表面试题进行进阶阶段的学习，通过具体的题目，我们能够深刻的理解链表，并且可以学习到一些常用的思想。
1、从尾到头打印链表
题目：输入一个链表的头结点，从尾到头翻过来打印出每个结点的值。
注意：这个题目并不是链表的反转，这里只是将链表从尾到头打印出来，对链表并没有作任何操作，链表还是原来的链表。
链表结点定义如下：
struct ListNode{
int m_nKey;
ListNode* m_pNext;
}
答案：网上有人说三种方法可以解决该问题，附上链接：三种方法实现从尾到头打印链表
这里我们只介绍两种：借用栈倒序输出链表和递归实现。
（1）借用栈倒序输出链表
解决这个问题我们首先想到的是遍历链表，遍历的顺序是从头到尾，而输出的顺序是从尾到头， 即第一个遍历的结点最后一个输出，最后一个遍历的结点第一个输出，这是典型的“后进先出”，所以我们可以借助栈实现这种顺序。
这里需要注意的有以下两点：
1、我们对于链表的认识：链表我们只需要知道一个头结点，那么我们就可以知道整个链表，因为头结点里面包含着指向下一个结点的指针，所以我们上边定义一个栈的操作后，重新定义一个头结点＝题目中的链表的头结点，那么就相当于我们拿到了题目中的链表。
2、在压栈和弹栈的过程中，我们先进行取栈顶的结点的操作，在打印完成后，我们还需要进行弹栈操作，不然打印的始终是栈顶的同一个结点（也就是链表的最后一个结点）！
（2）递归实现
这里需要注意的是当链表非常长的时候，会导致函数调用的层级很深，占用很多的资源，有可能导致函数调用栈溢出，显然用栈基于循环实现的代码（即第一个方法）的健壮性要好一些。
这里我们还理解了“递归在本质上是一个栈结构”（不知道后边的解释是不是清楚，大家权且看一下吧）
递归本质上是一个栈结构：就上边的这个递归举例，我们可以看到“调用自己形成循环”的这一步该函数调用了自己，相当于欠套了一层我们的函数方法，直至调用到链表的最后一个结点，比方我们的链表是有5个结点，那么到调用到第5个的时候，实际上我们的代码已经套用了5层，调用了5遍函数方法，（这其实就是“压栈”的过程）写出来的话，会有很大一堆，然后判断最后一个结点没有指向的结点了，那么开始返回，从第5层开始一层层的往外层方法返回，虽然我们的函数返回的是一个void，但是也是会返回的，直至返回到我们的第1层函数（这其实就是“弹栈”的过程）。所以我们得出结论：递归在本质上是一个栈结构。
2.1、反转链表
既然上边我们提到了链表的反转，那么我们就来看一下链表的反转到底是怎么实现的。
题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
链表结点定义如下：
struct ListNode{
int m_nKey;
ListNode* m_pNext;
}
通过下边的图，我们进行解释：
由于结点i的m_pNext指向了它的前一个结点，导致我们无法在链表中遍历到结点j，为了避免链表在结点i处断开，我们需要在调整结点i的m_pNext之前，把结点j保存下来，所以我们需要的结点有3个：结点i、前一个结点h，后一个结点j，相应我们需要定义3个指针。
注意：以下情况在写反转的过程中需要注意。
1、输入的链表头指针是NULL的情况；
2、输入的链表只有一个结点的情况；
3、输入的链表有多个结点。
其实这里写的代码并不多，实际理解过程中，建议大家手写一个简单的1234链表按照循环过程一步一步的画一画比较容易理解。
2.2字符串反转
OC中字符串的反转方式可以用两种方式来处理：
第一种：从头到尾取出字符串的每一个字符，然后将其从尾到头添加到可变的字符串中，最后输出即可。
第二种：将OC内部的字符串转换为C语言中的字符串，然后动态分配一个数组，然后将字符串内容拷贝到数组中，进行首尾交换操作。共进行数组长度/2次操作。
第一种方法的代码：（像压栈和弹栈的思想）
第二种方法的代码：
3、合并两个排序的链表
题目：输入两个递增的排序链表，合并这两个链表使新链表中的结点仍然是按照递增排序的。
链表结点定义如下：
struct ListNode{
int m_nKey;
ListNode* m_pNext;
}
我们按照题目的要求，可以画出如下图的简单示意图，链表1和链表2合并后形成链表3.
合并的过程需要有一个比较的过程，谁是头结点，谁是第二个结点...过程如下图：
这个过程我们可以分析得到链表1和链表2的头结点比较，然后小的最为新的链表的头结点，然后剩余的递增的链表我们命名为链表1'和链表2'，两个新的链表再比较头结点，比较出来后，又会出现两个新的链表1''和2''，依旧进行比较...这样我们会发现这其实是一个典型的递归过程，我们可以用递归函数完成合并过程。
当然在这个过程中，我们还要考虑到如果开始的链表1或者链表2是空链表的情况，但凡其中一个为空，那么合并的结果就是不为空的那个链表。如果两个都为空，合并出来还是空的，属于上边返回一个链表的情况。
4、链表中倒数第k个结点
题目：输入一个链表，输出该链表中倒数第k个结点。
思路：我们走到链表的尾端，往回走k个结点就可以得到倒数第k个结点。但是单链表只有指向后边的指针，没有向前指的指针，所以这个思路暂且不通。
那么我们想到，如果链表一共有n个结点的话，倒数第k个结点也就是正数第n－k＋1个结点，打比方一共有7个结点，那么倒数点3个，就是正数第（7-3+1）＝第5个结点。所以我们只要知道链表的结点个数n，然后再找到第n－k＋1个结点即可。那样的话就是遍历两遍，首先遍历得到n，再遍历走到n－k＋1个结点，得到倒数第k个结点，那我们有没有办法优化一下，只遍历一遍呢？
这里我们就引入“快慢指针”的概念。
笼统的解释一下这个“快慢指针”，简单的说就是设定两个指针a、b，两个指针分别指向头结点，打比方让a每次移动两步，让b每次移动一步，那么a就是“快指针”，b就是“慢指针”，比方链表不是循环链表，那么a走到尾端，b才走到中间的位置，这里不考虑奇偶，我们设定一个链表的结点数是3个，那么我们的头结点就是1，（这里需要说明的是我们还是要理解清楚“头结点”和“头指针”的区别，头指针是指向头结点的指针，只是一个指针，而头结点是一个结点，包含数据域和指针域，这里我们设定的链表，头结点就是1，所以a、b指针开始的时候都是指向结点1的）那么我们的a从1走到3的结点的位置，a就到了链表的尾端，b呢，从1走到了2的的结点的位置，那么我们就可以利用这个“快慢指针”找到所谓的“中位数”是哪个结点，仅仅遍历一次。
再举例，一个环形的链表，即循环链表，同样的我们设定两个指针a、b，打比方让a每次移动两步，让b每次移动一步，那么a和b最终有相遇的那么一刻，在某一个结点的时候两者的数据域是一样的，而且两者的指针是指向同一个的下一个结点。这样我们就可以反过来证明如果有一个链表，不告诉你是不是循环链表，让你证明是不是循环链表，那我们我们就可以用这个“快慢指针”的方法来证明。
这里附上快慢指针在链表的应用，大家可以参考一下。谢谢作者lostman。
言归正传，我们回到我们的这个“链表中倒数第k个结点”的问题上，根据上边说的快慢指针的思想我们可以设定两个指针a、b，同样的都指向头结点，让a先走上两步，再让b开始走，两者每次都是移动一个结点，那么当a到了尾结点的时候，b恰好指到的是倒数第3个结点的位置，那么怎么让b恰好指到倒数第k个结点的位置呢？我们叫a先走k－1步，再两者同步走，那么当a到达尾结点的时候，b指向的是正数n－（k－1）的结点，也就是正数n－k＋1的结点的位置，也就是倒数第k个结点的位置。
注意：根据前面的反转链表等一些题目，在这里我们也需要考虑链表是不是为空，还有就是k＝0的情况，还有就是总结点数n<k的情况。想一想前面这3个问题，如果不考虑到的话，很有可能造成我们的程序崩溃。
5、两个链表的第一个公共结点
题目：输入两个链表，找出它们的第一个公共结点。
示意图：
蛮力法：遍历第一个链表上每一个结点，每遍历一个结点，遍历一遍第二个链表，进行进行比较是否相同，如果相同，那么就找到了第一个公共结点；如果不同，继续遍历。时间复杂度O(mn)。
栈方法：我们可以想到，有“第一个公共结点”，那么就有大于等于1个公共结点，那么我们是不是可以先到尾结点那里，比较两个链表，如果相同，就弹走，直到两个不同的结点，那么弹走的那个结点就是第一个公共结点，“后进先出”，这个方法需要设置两个栈，时间复杂度O(m+n)，用空间消耗换取了时间效率。
彻底提高效率的方法(快慢指针法)：先得到两个链表的长度，一个长，一个短，那么先让长的走（长－短）步，然后两者在一起走，那么走到两个结点相等的时候，就恰好是“第一个公共结点”。时间复杂度O(m+n)，但是没有用到栈。
首先我们先写一个获取链表长度的方法，以便使用。
我们开始找第一个公共结点。
同样过程中我们需要考虑链表是不是为空等特殊情况。
我们将上边的示意图逆时针旋转90°，是不是发现，这是树！不过是叶结点指向了根结点的树。两个链表的第一个公共结点正好是二叉树中两个叶结点的最低公共祖先。
参考资料：《大话数据结构》作者：程杰。清华大学出版社。
《剑指offer》作者：何海涛。电子工业出版社。
最后，哪里不对的地方可以给我留言，我会及时改进的，谢谢大家。
