大家好，我是讯享网，很高兴认识大家。



前面几篇文章主要是讲了线性表，线性表是四种逻辑结构（集合结构、线性结构、树结构、图结构）的一种。任何一种逻辑结构，都是通过两种物理结构（顺序存储、链式存储）来在内存中实现的，线性表也不例外。在前面的几篇文章中，我们既讲了线性表的顺序存储，也讲了线性表的链式存储。在线性表的链式存储中，我们又细分了单向链表、单向循环链表、双向链表、双向循环链表。如下图所示：

顺序存储最大的优势就是可以快速读取指定位置的元素，它的弊端是做增删的时候后面的元素都需要移位；链式存储最大的优势是它做增删很迅速，只需要改变指针域的指向即可，其劣势是每一次查找都需要遍历。

今天我们这篇文章，就是通过几道题目，来巩固一下对线性表的理解。话不多说，直接开干。

本篇文章中的所有涉及到链表的题目，都是使用的单项链表。关于单向链表的创建、打印和插入的代码如下：

题目一

题目1：

将两个递增的有序链表合并为一个有序链表。要求：结果链表仍然使用两个链表的存储空间，不再另外占用其他的链表空间；并且表中不能有重复数据。

题目分析：

（1）两个链表均是有序递增的，因此对两条链表进行一次遍历即可

（2）最终合成的链表中不能有重复的数据，因此要及时移除重复项

（3）要求不额外占用空间，意思就是不能建立新的节点，因此要在原链表上进行操作

（4）生成的新的链表是一个有序链表，它没有说是有序递增还是有序递减。如果是有序递增，则则使用后插法；如果是有序递减，则使用前插法。

逻辑设计：

（1）两个待合并的递增的有序链表是listA和listB，使用listC来记录结果链表，让listC复用listA的头结点，并使用elementC来记录listC的最后一个节点

（2）同时循环遍历listA和listB，并分别使用elementA和elementB来记录当前遍历到的节点。然后让elementC的指针域指向数值较小的那个节点；如果数值相等，则让elementC的指针域指向其中一个节点，并注意移除另外一个节点

（3）当遍历完其中一条链表的时候会跳出循环，因此还要将剩下那条链表中的元素依次拼接到listC上面

（4）释放listB的头结点

代码如下：

验证代码如下：

题目二

题目2：

已知两个链表A和B分别表示两个集合，其元素递增排列。请设计一个算法，用于求出A和B的交集，并存储在A链表中。

题目分析：

（1）A和B两个链表都是有序递增的，所以可以直接遍历一遍即可

（2）求交集，意思是找到相同的元素，然后保留其中一个节点，其他的节点都释放

（3）最终的结果存在A链表中，说明需要复用链表A的头结点

逻辑设计：

（1）链表A、B分别使用listA、listB来表示，交集使用listC来表示

（2）将listC的头结点设置为listA的头结点，并且使用临时变量tailNodeC来表示listC的最后一个节点

（3）遍历listA和listB，找到值相等的节点，然后tailNodeC的指针域指向其中一个节点，另一个销毁，并且注意更新tailNodeC的指向；其他的较小的节点也销毁

（4）直到有一条链表到头了，那么就跳出循环，然后将剩余的那条链表中的元素都给销毁

（5）将交集链表的尾结点的指针域置空，并且将链表B的头结点销毁

代码如下：

验证代码如下：

题目三

题目3：

将链表中的所有节点的链接方向”原地旋转“，要求只能利用原表的存储空间。

例如:L={0,2,4,6,8,10}, 逆转后: L = {10,8,6,4,2,0};

题目分析：

（1）只能利用原表的存储空间，说明不能开辟新的节点，但是可以新增临时的指针变量

（2）初步想法是，通过一个临时指针变量来记录原链表的节点，然后遍历原链表，依次将遍历到的节点插入到原链表首元结点的位置（前插法）。

（3）其实，原地旋转也就是所谓的逆序，而链表的前插法就是第一个插入进来的节点最终会置于链表的最后，这也是所谓的逆序。原地旋转、逆序、前插法这几个词是对应的。

逻辑设计：

（1）新建一个节点指针变量tempNode，并让其指向原链表的首元结点

（2）通过tempNode来遍历链表

（3）将每一次遍历的节点都插入到原链表首元结点的位置（前插法），注意修改该节点的后继节点

代码如下：

验证代码如下：

题目四

题目4：

设计一个算法，删除递增有序链表中值大于等于min且小于等于max（min、max是给定的两个参数，其值可以与表中的元素相同，也可以不同）的所有元素。

题目分析：

（1）该链表是递增有序链表，因此可以直接遍历找到符合范围的两个边界节点

（2）将两个边界节点通过指针域连接起来

（3）依次遍历销毁两个边界节点之间的各个节点

逻辑设计：

讯享网

（1）通过两个遍历，分别找到值大于等于min的第一个节点前面的那个节点priorNode，以及值小于等于max的最后那个节点tailNode

（2）找到priorNode的后继节点（即待移除的第一个节点），并使用变量toDeleteHeadNode来记录

（3）将priorNode的后继设置为tailNode的后继

（4）依次遍历移除toDeleteHeadNode和tailNode之间的所有节点

代码如下：

上述算法的时间复杂度是O(n)，空间复杂度是O(1)。其中，n是链表长度。

验证代码如下：

题目五

题目5：

假设将n(n>1)个整数存放到一维数组R中，请设计一个在时间和空间两方面都尽可能高效的算法，

将R中保存的序列循环左移p个位置(0<p<n)个位置， 即将R中的数据由(x0,x1,……,xn-1)变换为(xp,xp+1,…,xn-1,x0,x1,…,xp-1).

题目分析：

例如: array[10] = {0,1,2,3,4,5,6,7,8,9},

n = 10，p = 3;

pre[10] = {3,4,5,6,7,8,9,0,1,2}

这里考察的是线性表的顺序存储。

逻辑设计：

（1）先将原数组完全翻转

（2）再将翻转后的数组通过位置分成两段进行翻转

（3）将顺序表的翻转算法抽离出来，抽离的时候需要暴露出翻转的初始位置和结束位置

代码如下：

上述算法的时间复杂度是O(n)，空间复杂度是O(1)。其中，n是数组长度。

验证代码如下：

题目六

题目6：

已知一个整数序列A = (a0,a1,a2,…an-1)，其中(0<= ai <=n),(0<= i<=n). 若存在ap1= ap2 = …= apm = x,且m>n/2(0<=pk<n,1<=k<=m),则称x 为 A的主元素. 例如,A = (0,5,5,3,5,7,5,5),则5是主元素; 若B = (0,5,5,3,5,1,5,7),则A 中没有主元素,假设A中的n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出数组元素中的主元素,若存在主元素则输出该元素,否则输出-1.

题目分析：

（1）本题目就是在一个数组中去寻找主元素，也就是说，找到个数占数组长度一半以上的元素并输出，如果没有找到的话则输出-1。

（2）设计算法的时候，可以让一个主元素跟一个非主元素配对，最后没有其他元素与之匹配的那些元素就是主元素

逻辑设计：

（1）通过变量mainElement来记录主元素，通过count来记录主元素与其他非主元素抵消之后剩余的个数

（2）自数组中第1个元素开始循环遍历数组，在每一次循环体中执行的逻辑如下

①如果count==0，则设置当前遍历到的值为mainElement，并且设置count为1

②如果count>0，如果当前遍历到的值与mainElement相等，则count加1

③如果count>0，如果当前遍历到的值与mainElement不相等，则count减1

（3）遍历完之后，如果count大于0，则拿到mainElement，再循环遍历一遍来获取到mainElement出现的次数，如果该次数大于数组总长度的一般，那么就为主元素。

代码如下：

上述算法的时间复杂度是O(listLength)，空间复杂度是O(1)。其中，listLength是数组的长度。

验证代码如下：

题目七

题目7：

用单链表保存m个整数, 结点的结构为(data,link),且|data|<=n(n为正整数). 现在要去设计一个时间复杂度尽可能高效的算法. 对于链表中的data 绝对值相等的结点, 仅保留第一次出现的结点,而删除其余绝对值相等的结点.例如,链表A = {21,-15,15,-7,15}, 删除后的链表A={21,-15,-7};

题目分析：

（1）本题要求时间复杂度尽可能高，这意味着我们可以利用空间换时间，也就是说只要能保证时间复杂度高，那么空间复杂度是不需要考虑的

（2）由于|data|<=n，所以可以创建一个长度为n+1的数组，数组的元素初始值均设置为0，该数组用于记录单链表中的节点值的绝对值出现的频次

逻辑设计：

（1）假设单链表是linkedList，链表长度是m，要求链表中的数值的绝对值都不能大于n

（2）创建一个长度为n+1的一位数组array，利用该数组的index表示linkedList中的各个节点上的值的绝对值，array各个位置上的初始值均设置为0，这样就表示各个值暂时均未出现过

（3）自首元结点开始遍历，获取到遍历到的节点的值的绝对值currentValue，然后找到array[currentValue]的值，如果该值为0，则将该值设置为1，然后进行下一次遍历；如果该值为1，则将当前节点销毁，然后遍历下一节点。

（4）在上面遍历的过程中，要注意调整销毁节点以及其前驱结点的后继。

代码如下：

上述代码的时间复杂度是O(m)，空间复杂度是O(limitedValue)。其中m指的是链表的长度，limitedValue指的是链表中各节点值的绝对值的最大值。

验证代码如下：

以上。