数据结构与算法（五）——链表相关算法题目
前面几篇文章主要是讲了线性表，线性表是四种逻辑结构（集合结构、线性结构、树结构、图结构）的一种。任何一种逻辑结构，都是通过两种物理结构（顺序存储、链式存储）来在内存中实现的，线性表也不例外。在前面的几篇文章中，我们既讲了线性表的顺序存储，也讲了线性表的链式存储。在线性表的链式存储中，我们又细分了单向链表、单向循环链表、双向链表、双向循环链表。如下图所示：
顺序存储最大的优势就是可以快速读取指定位置的元素，它的弊端是做增删的时候后面的元素都需要移位；链式存储最大的优势是它做增删很迅速，只需要改变指针域的指向即可，其劣势是每一次查找都需要遍历。
今天我们这篇文章，就是通过几道题目，来巩固一下对线性表的理解。话不多说，直接开干。
本篇文章中的所有涉及到链表的题目，都是使用的单项链表。关于单向链表的创建、打印和插入的代码如下：
#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
// 操作的状态
typedef enum : int {
Success,
Error,
} Status;
// 数据类型
typedef int ElementType;
// 节点结构
typedef struct Node{
ElementType data; // 数据域
struct Node *next; // 指针域
} Node;
// 链表类型
typedef struct Node * LinkedList;
// 创建一个带有头结点的单向链表
Status createLinkedList(LinkedList *list) {
// 新建节点
LinkedList headNode = malloc(sizeof(Node));
if (!headNode) {
return Error;
}
headNode->data = -1;
headNode->next = NULL;
// 将新节点设置为链表的头结点
*list = headNode;
return Success;
}
// 打印链表
Status printLinkedList(LinkedList list) {
if (!list) {
printf("该链表不存在\n");
return Error;
}
LinkedList node = list->next;
if (!node) {
printf("该链表为空\n");
return Success;
}
printf("链表信息如下：\n");
while (node) {
printf("%d\n", node->data);
node = node->next;
}
return Success;
}
// 往单链表中插入元素
Status insertElement(LinkedList *list, int index, ElementType element) {
// 如果链表为空则直接报错
if (!(*list)) {
return Error;
}
// 校验坐标的有效性
if (index < 1) {
return Error;
}
// 找到待插入位置前面的节点（如果待插入位置超过链表长度，则直接插入到链表尾部）
LinkedList priorNode = *list;
for (int i = 1; i < index && priorNode->next; i++, priorNode = priorNode->next);
// 新建节点
LinkedList node = malloc(sizeof(Node));
node->data = element;
// 找到在当前待插入位置上的节点
LinkedList nextNode = priorNode->next;
// 将新节点加入到链表中
node->next = nextNode;
priorNode->next = node;
return Success;
}题目一
题目1：
将两个递增的有序链表合并为一个有序链表。要求：结果链表仍然使用两个链表的存储空间，不再另外占用其他的链表空间；并且表中不能有重复数据。
题目分析：
（1）两个链表均是有序递增的，因此对两条链表进行一次遍历即可
（2）最终合成的链表中不能有重复的数据，因此要及时移除重复项
（3）要求不额外占用空间，意思就是不能建立新的节点，因此要在原链表上进行操作
（4）生成的新的链表是一个有序链表，它没有说是有序递增还是有序递减。如果是有序递增，则则使用后插法；如果是有序递减，则使用前插法。
逻辑设计：
（1）两个待合并的递增的有序链表是listA和listB，使用listC来记录结果链表，让listC复用listA的头结点，并使用elementC来记录listC的最后一个节点
（2）同时循环遍历listA和listB，并分别使用elementA和elementB来记录当前遍历到的节点。然后让elementC的指针域指向数值较小的那个节点；如果数值相等，则让elementC的指针域指向其中一个节点，并注意移除另外一个节点
（3）当遍历完其中一条链表的时候会跳出循环，因此还要将剩下那条链表中的元素依次拼接到listC上面
（4）释放listB的头结点
代码如下：
void mergeLists(LinkedList listA, LinkedList listB, LinkedList *resultList) {
// 复用链表A的头结点
LinkedList listC = listA;
// 记录结果链表中的最后一个节点
LinkedList tailNodeC = listC;
// 自头结点开始遍历链表A和链表B
LinkedList nodeA = listA->next;
LinkedList nodeB = listB->next;
while (nodeA && nodeB) {
if (nodeA->data < nodeB->data) {
tailNodeC->next = nodeA;
tailNodeC = nodeA; // taiNodeC是记录的结果链表中的最后一个节点
nodeA = nodeA->next;
} else if (nodeB->data < nodeA->data) {
tailNodeC->next = nodeB;
tailNodeC = nodeB;
nodeB = nodeB->next;
} else {
// 当链表中元素相等的时候，只取用其中一个，其余的都销毁
tailNodeC->next = nodeA;
tailNodeC = nodeA;
nodeA = nodeA->next;
// 销毁另外一个节点
LinkedList tempNode = nodeB;
nodeB = nodeB->next;
free(tempNode);
}
}
// 将余下的节点拼接到结果链表上
if (nodeA) {
tailNodeC->next = nodeA;
}
if (nodeB) {
tailNodeC->next = nodeB;
}
// 释放链表B的头结点
free(listB);
*resultList = listC;
}验证代码如下：
LinkedList listA;
LinkedList listB;
createLinkedList(&listA);
createLinkedList(&listB);
for (int i = 1; i < 10; i++) {
insertElement(&listA, i, 2*i);
}
for (int i = 1; i < 10; i++) {
insertElement(&listB, i, 3*i);
}
printLinkedList(listA);
printLinkedList(listB);
LinkedList listC;
mergeLists(listA, listB, &listC);
printLinkedList(listC);题目二
题目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的头结点销毁
代码如下：
void interSectionOf(LinkedList listA, LinkedList listB, LinkedList *resultList) {
// 交集链表复用链表A的头结点
LinkedList listC = listA;
// 记录交集链表中的最后一个节点
LinkedList tailNodeC = listC;
// 循环遍历链表A和B
LinkedList nodeA = listA->next;
LinkedList nodeB = listB->next;
LinkedList tempNode;
while (nodeA && nodeB) {
// 销毁值较小的节点
if (nodeA->data < nodeB->data) {
tempNode = nodeA;
nodeA = nodeA->next;
free(tempNode);
} else if (nodeB->data < nodeA->data) {
tempNode = nodeB;
nodeB = nodeB->next;
free(tempNode);
} else {
//如果值相等，则保留其中一个节点，另外一个节点销毁
tailNodeC->next = nodeA;
tailNodeC = nodeA; // 更新交集链表的尾结点
nodeA = nodeA->next;
tempNode = nodeB;
nodeB = nodeB->next;
free(tempNode);
}
}
// 当其中一条链表遍历完的时候跳出循环，然后将余下的那条链表中的剩余节点都清空
while (nodeA) {
tempNode = nodeA;
nodeA = nodeA->next;
free(tempNode);
}
while (nodeB) {
tempNode = nodeB;
nodeB = nodeB->next;
free(tempNode);
}
//将交集链表的尾结点的指针域置空
tailNodeC->next = NULL;
// 销毁链表B的头结点
free(listB);
*resultList = listC;
}验证代码如下：
LinkedList listA;
LinkedList listB;
createLinkedList(&listA);
createLinkedList(&listB);
for (int i = 1; i < 10; i++) {
insertElement(&listA, i, 2*i);
}
for (int i = 1; i < 10; i++) {
insertElement(&listB, i, 3*i);
}
printLinkedList(listA);
printLinkedList(listB);
LinkedList listC;
interSectionOf(listA, listB, &listC);
printLinkedList(listC);
题目三
题目3：
将链表中的所有节点的链接方向”原地旋转“，要求只能利用原表的存储空间。
例如:L={0,2,4,6,8,10}, 逆转后: L = {10,8,6,4,2,0};
题目分析：
（1）只能利用原表的存储空间，说明不能开辟新的节点，但是可以新增临时的指针变量
（2）初步想法是，通过一个临时指针变量来记录原链表的节点，然后遍历原链表，依次将遍历到的节点插入到原链表首元结点的位置（前插法）。
（3）其实，原地旋转也就是所谓的逆序，而链表的前插法就是第一个插入进来的节点最终会置于链表的最后，这也是所谓的逆序。原地旋转、逆序、前插法这几个词是对应的。
逻辑设计：
（1）新建一个节点指针变量tempNode，并让其指向原链表的首元结点
（2）通过tempNode来遍历链表
（3）将每一次遍历的节点都插入到原链表首元结点的位置（前插法），注意修改该节点的后继节点
代码如下：
void reverseLinkedList(LinkedList *list) {
// 记录原链表的首元节点
LinkedList currentNode = (*list)->next;
LinkedList tempNode;
// 将原链表的头结点与其他节点断开
(*list)->next = NULL;
// 自首元结点开始遍历原链表
while (currentNode) {
// 将当前遍历到的节点插入到首元结点的位置
tempNode = currentNode->next;
currentNode->next = (*list)->next;
(*list)->next = currentNode;
// 更新遍历的节点位置
currentNode = tempNode;
}
}验证代码如下：
LinkedList listA;
createLinkedList(&listA);
for (int i = 1; i < 10; i++) {
insertElement(&listA, i, 2*i);
}
printLinkedList(listA);
reverseLinkedList(&listA);
printLinkedList(listA);题目四
题目4：
设计一个算法，删除递增有序链表中值大于等于min且小于等于max（min、max是给定的两个参数，其值可以与表中的元素相同，也可以不同）的所有元素。
题目分析：
（1）该链表是递增有序链表，因此可以直接遍历找到符合范围的两个边界节点
（2）将两个边界节点通过指针域连接起来
（3）依次遍历销毁两个边界节点之间的各个节点
逻辑设计：
（1）通过两个遍历，分别找到值大于等于min的第一个节点前面的那个节点priorNode，以及值小于等于max的最后那个节点tailNode
（2）找到priorNode的后继节点（即待移除的第一个节点），并使用变量toDeleteHeadNode来记录
（3）将priorNode的后继设置为tailNode的后继
（4）依次遍历移除toDeleteHeadNode和tailNode之间的所有节点
代码如下：
void removeNodesBetween(LinkedList *list, int min, int max) {
// 检验输入范围的有效性
if (min > max) {
return;
}
// 如果链表元素为空，则直接返回
if (!(*list) || !(*list)->next) {
return;
}
LinkedList priorNode = *list;
LinkedList toDeleteHeadNode;
LinkedList toDeleteTailNode = (*list)->next;
// 寻找第一个大于等于min的节点之前的那个节点
while ((priorNode->next) && (priorNode->next->data < min)) {
priorNode = priorNode->next;
}
// 获取待删除的第一个节点
toDeleteHeadNode = priorNode->next;
// 寻找最后一个小于等于max的节点
while ((toDeleteTailNode->next) && (toDeleteTailNode->next->data <= max)) {
toDeleteTailNode = toDeleteTailNode->next;
}
// 验证寻找到的边界节点
if (toDeleteHeadNode->data < min || toDeleteTailNode->data > max) {
return;
}
// 连接两个边界节点
priorNode->next = toDeleteTailNode->next;
// 依次释放待删除节点
LinkedList tempNode;
while (toDeleteHeadNode != toDeleteTailNode) {
tempNode = toDeleteHeadNode;
toDeleteHeadNode = toDeleteHeadNode->next;
free(tempNode);
}
}上述算法的时间复杂度是O(n)，空间复杂度是O(1)。其中，n是链表长度。
验证代码如下：
LinkedList listA;
createLinkedList(&listA);
for (int i = 1; i < 10; i++) {
insertElement(&listA, i, 2*i);
}
printLinkedList(listA);
removeNodesBetween(&listA, 0,1);
printLinkedList(listA);题目五
题目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）将顺序表的翻转算法抽离出来，抽离的时候需要暴露出翻转的初始位置和结束位置
代码如下：
// 数组中某个范围内的元素翻转
void reverseDecequenceList(int *list, int start, int end) {
int left = start;
int right = end;
int temp;
while (left < right) {
// 交换
temp = list[left];
list[left] = list[right];
list[right] = temp;
left++;
right--;
}
}
void transport(int *list, int listLength, int index) {
// 如果左移的位置超过数组长度，或者左移小于等于0位，那么就直接退出本次函数执行
if (index >= listLength || index <= 0) {
return;
}
// 先将整个数组翻转
reverseDecequenceList(list, 0, listLength-1);
// 分段翻转
reverseDecequenceList(list, 0, listLength-index-1);
reverseDecequenceList(list, listLength-index, listLength-1);
}上述算法的时间复杂度是O(n)，空间复杂度是O(1)。其中，n是数组长度。
验证代码如下：
int listA[9] = {1,2,3,4,5,6,7,8,9};
transport(listA, 9, 3);
for (int i = 0; i < 9; i++) {
printf("%d", listA[i]);
}题目六
题目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出现的次数，如果该次数大于数组总长度的一般，那么就为主元素。
代码如下：
int getMainElement(int *list, int listLength){
// 使用mainElement来记录主元素的值
int mainElement = -1;
int count = 0;
// 找到主元素，以及主元素与非主元素的个数差
int currentValue;
for (int i = 0; i < listLength; i++) {
currentValue = list[i];
if (count > 0) {
currentValue == mainElement ? count++ : count--;
} else {
mainElement = currentValue;
count = 1;
}
}
// 当个数差为零的时候说明没有主元素
if (count <= 0) {
return -1;
}
// 重新遍历，以获取mainElement在数组中真正出现的次数
count = 0;
for (int i = 0; i < listLength; i++) {
list[i] != mainElement ?: count++;
}
// 只有当出现次数大于一半的时候才会是主元素，否则不是主元素
if (count > listLength/2) {
return mainElement;
} else {
return -1;
}
}上述算法的时间复杂度是O(listLength)，空间复杂度是O(1)。其中，listLength是数组的长度。
验证代码如下：
int list[10] = {1,2,6,6,6,6,6,3,4,5};
printf("%d", getMainElement(list, 11));题目七
题目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）在上面遍历的过程中，要注意调整销毁节点以及其前驱结点的后继。
代码如下：
void filterLinkedList(LinkedList *list, int limitedValue) {
// 链表为空的时候直接返回
if (!(*list) || !(*list)->next) {
return;
}
// 新建数组array，并初始化所有元素值为0，以记录链表节点绝对值出现的次数
int array[limitedValue + 1];
for (int i = 0; i < limitedValue + 1; i++) {
array[i] = 0;
}
LinkedList node = *list;
LinkedList tempNode;
while (node->next) {
int currentValue = abs(node->next->data);
int flag = array[currentValue];
if (flag == 0) {
// 该节点上的值之前没出现过，则标记一下
array[currentValue] = 1;
node = node->next;
} else {
// 该节点上的值之前出现过，则从链表中移除该节点，并释放该节点的内存
tempNode = node->next;
node->next = node->next->next;
free(tempNode);
}
}
}
上述代码的时间复杂度是O(m)，空间复杂度是O(limitedValue)。其中m指的是链表的长度，limitedValue指的是链表中各节点值的绝对值的最大值。
验证代码如下：
LinkedList listA;
createLinkedList(&listA);
insertElement(&listA, 1, -10);
insertElement(&listA, 2, 8);
insertElement(&listA, 3, -6);
insertElement(&listA, 4, 4);
insertElement(&listA, 5, -2);
insertElement(&listA, 6, 0);
insertElement(&listA, 7, 2);
insertElement(&listA, 8, -4);
insertElement(&listA, 9, 6);
insertElement(&listA, 10, -8);
printLinkedList(listA);
filterLinkedList(&listA, 10);
printLinkedList(listA);以上。
腾讯云开发者
