C 408—《数据结构》算法题底子篇—链表（下）

用多少眼泪才能让你相信 · 2024-10-15 22:58:24

目次
Δ前言
一、两个升序链表归并为一个降序链表
0.题目：
1.算法设计思想：
2.C语言形貌：
3.算法的时间和空间复杂度：
二、两个链表的所有相同值结点天生一个新链表
0.题目：
1.算法设计思想：
2.C语言形貌：
3.算法的时间和空间复杂度：
三、两个链表的所有相同值结点放入到其中一个原链表中
0.题目：
1.算法设计思想：
2.C语言形貌：
3.算法的时间和空间复杂度：
四、判定一个链表是否为另一个链表的连续子序列
0.题目：
1.算法设计思想：
2.C语言形貌：
3.算法的时间和空间复杂度：
五、判定一个循环双链表是否对称
0.题目：
1.算法设计思想：
2.C语言形貌：
3.算法的时间和空间复杂度：
六、两个循环单链表的连接 (链接)
0.题目：
1.算法设计思想：
2.C语言形貌：
3.算法的时间和空间复杂度：
七、循环单链表反复找到最小值结点并删除
0.题目：
1.算法设计思想：
2.C语言形貌：
3.算法的时间和空间复杂度：
八、非循环双链表查改结点并按照结点访问频度举行排序
0.题目：
1.算法设计思想：
2.C语言形貌：
3.算法的时间和空间复杂度：
九、查找单链表中倒数第K个结点 [2009真题]
0.题目：
1.算法设计思想：
2.C语言形貌：
3.算法的时间和空间复杂度：
十、两个链表存储两个单词求共同后缀的起始位置 [2012真题]
0.题目：
1.算法设计思想：
2.C语言形貌：
3.算法的时间和空间复杂度：
十一、链表绝对值的去重 [2015真题]
0.题目：
1.算法设计思想：
2.C语言形貌：
3.算法的时间和空间复杂度：
十二、链表元素的重新交织分列 [2019真题]
0.题目：
1.算法设计思想：
2.C语言形貌：
3.算法的时间和空间复杂度：
Δ总结

Δ前言

从408应试的角度来看，算法题主要分为四部分——①线性表(包罗数组和链表)；②二叉树；③图；④查找。本篇博文主要讲链表相关的底子算法（由于链表相关的算法题目较多，所以up分为了上下两篇博文）。
博文中涉及到的题目全部参考自《王道数据结构考研复习指导》和《竟成408考研复习全书》。
注意事项——①点击文章侧边栏目次大概文章开头的目次可以举行跳转。②所有题目都符合408算法题的题目格式，即第一问算法设计思想、第二问C语言形貌该算法、第三问盘算该算法的时空复杂度。
良工不示人以朴，up所有文章都会适时补充完满。各人假如有问题都可以在批评区举行交换大概私信up。感谢阅读！

一、两个升序链表归并为一个降序链表

0.题目：

   已知有两个升序的单链表（按照结点的值递增排序），现要求将这两个升序的单链表归并为一个降序的单链表，而且要求除了原本两个升序链表的结点外，在归并过程中不允许创建新的结点。
          请设计一个算法来实现上述操作，用C语言形貌该算法，而且盘算出该算法的时间复杂度和空间复杂度。
    1.算法设计思想：

   我们早在“C 408—《数据结构》算法题底子篇—数组”一文中就打仗过归并思想。它的算法思想是：重新到尾依次比较两个次序表中的元素，并把更小的谁人元素放在最终的次序表中，直到合并完毕；只不外如今从"次序表"换成"链表"了，在次序中我们是通过三个下标实现的，那么在链表中我们自然要通过三个指针来实现了。
    p1指针指向listA链表的结点，p2指针指向listB链表的结点。利用while循环遍历两个升序链表，每次将更小的谁人结点头插到新的链表中。（题干要求我们从“升序”变为“降序”，不难想到要用到头插法，因为头插法可以逆置链表）
    2.C语言形貌：

完整代码如下：(注意看解释)

#include <stdio.h>
#include <stdlib.h>
//Data Structure Defining
typedef struct LinkNode {
int data;
struct LinkNode * next;
} LinkNode, * LinkList;
//Functions Declaration
void initialize(LinkList * pHead);
LinkNode * createNewNode(int data);
void traverse(LinkList pHead);
void freeList(LinkList pHead);
void freeSingleNode(LinkNode * node);
LinkList mergeTwoList(LinkList listA, LinkList listB);
int main(void) {
//给定两个特定的升序链表，用于测试该算法。
LinkList listA,listB;
initialize(&listA);
initialize(&listB);
LinkNode * a1 = createNewNode(1);
LinkNode * a2 = createNewNode(2);
LinkNode * a3 = createNewNode(2);
LinkNode * a4 = createNewNode(3);
LinkNode * a5 = createNewNode(4);
LinkNode * a6 = createNewNode(5);
listA->next = a1;
a1->next = a2;
a2->next = a3;
a3->next = a4;
a4->next = a5;
a5->next = a6;
a6->next = NULL;
LinkNode * b1 = createNewNode(11);
LinkNode * b2 = createNewNode(77);
LinkNode * b3 = createNewNode(141);
listB->next = b1;
b1->next = b2;
b2->next = b3;
b3->next = NULL;
printf("\n在合并前，链表listA情况：");
traverse(listA);
printf("在合并前，链表listB情况：");
traverse(listB);
LinkList finalList = mergeTwoList(listA, listB);
printf("在合并后，降序链表finalList情况 —— ");
traverse(finalList);
printf("\n");
freeList(finalList);
freeSingleNode(listA);
freeSingleNode(listB);
return 0;
}
void initialize(LinkList * pHead) {
(*pHead) = (LinkNode * ) malloc(sizeof(LinkNode));
(*pHead)->data = 0;
(*pHead)->next = NULL;
}
LinkNode * createNewNode(int data) {
LinkNode * p = (LinkNode * ) malloc(sizeof(LinkNode));
p->data = data;
p->next = NULL;
return p;
}
void traverse(LinkList pHead) {
LinkNode * p = pHead->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void freeList(LinkList pHead) {
LinkNode * p = pHead;
LinkNode * temp;
while (p != NULL) {
temp = p;
p = p->next;
free(temp);
}
}
void freeSingleNode(LinkNode * node) {
free(node);
}
LinkList mergeTwoList(LinkList listA, LinkList listB) {
LinkList finalList;
initialize(&finalList);
LinkNode * p1 = listA->next;
LinkNode * p2 = listB->next;
LinkNode * temp; //定义temp指针是为了防止在头插的时候断链。
while (p1 != NULL && p2 != NULL) { //只要链表listA和listB中还有元素没有遍历完毕，就继续进行合并。
if (p1->data <= p2->data) { //注意——目标链表是降序链表,所以要先插小的。
temp = p1->next;
//进行头插
p1->next = finalList->next;
finalList->next = p1;
//恢复p1指针
p1 = temp;
} else {
temp = p2->next;
p2->next = finalList->next;
finalList->next = p2;
p2 = temp;
}
}
while (p1 != NULL) { //若listA中还有剩余的元素，就逐个头插到finalList中。
temp = p1->next;
p1->next = finalList->next;
finalList->next = p1;
p1 = temp;
}
while (p2 != NULL) { //若listB中还有剩余的元素，就逐个头插到finalList中。
temp = p2->next;
p2->next = finalList->next;
finalList->next = p2;
p2 = temp;
}
return finalList;
}

复制代码

运行结果：

3.算法的时间和空间复杂度：

   (1) 时间复杂度 :
    O(m + n). 这是合并两个链表的最佳时间复杂度.
(2) 空间复杂度 :
O(1). 因为我们没有创建新的结点(题目也不允许我们创建), 整个过程只利用了几个临时的辅助变量, 所以该算法是"原地工作"的.

二、两个链表的所有相同值结点天生一个新链表

0.题目：

   设listA和listB是两个带有头结点的单链表，且listA和listB都是升序链表（结点的值递增有序），现要求在不破坏原有链表结点的前提下，产生一个新链表listC，listC中保存的结点是listA和listB的相同值的结点（注意是值相同）。
          请设计一个算法来实现上述操作，用C语言形貌该算法，而且盘算出该算法的时间复杂度和空间复杂度。
    1.算法设计思想：

   题干中要求“不破坏原有链表结点”，阐明我们在遍历过程中需要创建新的结点。
    利用while循环遍历listA和listB链表，每次循环都要比较当前listA和listB结点的值的大小（预设p,q指针分别指向listA和listB当前的结点），若值不相等，令值更小的指针后移；若值相等，就创建一个与当前值相等的结点，并将该结点插入到listC链表中，随后同时移动p,q指针后移，当p,q指针某一方为NULL时，阐明对应的链表已经遍历完毕，此时结束while循环，返回listC链表。
    2.C语言形貌：

完整代码如下：(注意看解释)

#include <stdio.h>
#include <stdlib.h>
//Data Structure Defining
typedef struct LinkNode {
int data;
struct LinkNode * next;
} LinkNode, * LinkList;
//Functions Declaration
void initialize(LinkList * pHead);
LinkNode * createNewNode(int data);
void traverse(LinkList pHead);
void freeList(LinkList pHead);
LinkList findCommonValues(LinkList listA, LinkList listB);
int main(void) {
//给定两个特定的升序链表，用于测试该算法。
LinkList listA,listB;
initialize(&listA);
initialize(&listB);
LinkNode * a1 = createNewNode(1);
LinkNode * a2 = createNewNode(2);
LinkNode * a3 = createNewNode(2);
LinkNode * a4 = createNewNode(3);
LinkNode * a5 = createNewNode(5);
listA->next = a1;
a1->next = a2;
a2->next = a3;
a3->next = a4;
a4->next = a5;
a5->next = NULL;
LinkNode * b1 = createNewNode(2);
LinkNode * b2 = createNewNode(2);
LinkNode * b3 = createNewNode(3);
LinkNode * b4 = createNewNode(7);
listB->next = b1;
b1->next = b2;
b2->next = b3;
b3->next = b4;
b4->next = NULL;
printf("\n初始的升序链表listA情况: ");
traverse(listA);
printf("\n初始的升序链表listB情况: ");
traverse(listB);
LinkList listC = findCommonValues(listA, listB);
printf("\n维护有listA, listB公共值结点的listC链表情况: ");
traverse(listC);
freeList(listA);
freeList(listB);
freeList(listC);
return 0;
}
void initialize(LinkList * pHead) {
(*pHead) = (LinkNode * ) malloc(sizeof(LinkNode));
(*pHead)->data = 0;
(*pHead)->next = NULL;
}
LinkNode * createNewNode(int data) {
LinkNode * p = (LinkNode * ) malloc(sizeof(LinkNode));
p->data = data;
p->next = NULL;
return p;
}
void traverse(LinkList pHead) {
LinkNode * p = pHead->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void freeList(LinkList pHead) {
LinkNode * p = pHead;
LinkNode * temp;
while (p != NULL) {
temp = p;
p = p->next;
free(temp);
}
}
LinkList findCommonValues(LinkList listA, LinkList listB) {
LinkNode * p = listA->next;
LinkNode * q = listB->next;
LinkList listC;
initialize(&listC);
LinkNode * rear = listC; //listC链表的尾指针，用于实现共同值结点尾插到listC链表中。
while (p != NULL && q != NULL) {
if (p->data < q->data) {
p = p->next;
} else if (p->data > q->data) {
q = q->next;
} else {
//去重(Eliminates consecutive duplicates in the result list)
if (rear == listC || p->data != rear->data) {
LinkNode * commonValueNode = createNewNode(p->data);
rear->next = commonValueNode;
rear = commonValueNode;
}
p = p->next;
q = q->next;
}
}
/*
由于createNewNode方法中已经将新创建的结点的next指针域置空，所以最后不需要再处理尾链。
*/
return listC;
}

复制代码

运行结果 :

3.算法的时间和空间复杂度：

   (1) 时间复杂度 :
        The time complexity is O(n + m), where n and m are the lengths of listA and listB respectively. This is optimal for this problem.
    (2) 空间复杂度：
          The space complexity is O(min{n, m}) in the worst case, which is also optimal.

三、两个链表的所有相同值结点放入到其中一个原链表中

0.题目：

   已知两个升序的单链表listA和listB，要求将两个链表的所有公共值结点全部放入到单链表listA中。
          请设计一个算法来实现上述操作，用C语言形貌该算法，而且盘算出该算法的时间复杂度和空间复杂度。
    1.算法设计思想：

   此题要与上一题类比举行理解，上一题不允许我们破坏原有结点，所以我们需要创建新的结点来天生最终的链表，这就导致算法的空间复杂度更高了，达不到算法”原地工作“的结果。而此题中，要求我们用原来的链表listA维护所有的公共值结点，所以肯定涉及到了链表的删除，就需要我们在上一题的底子上做一些小小的改动。
    仍然利用while循环遍历listA和listB链表，对于listA链表，利用两个指针currentA和prevA分别指向listA链表的当前结点和前一个结点。每次循环都要比较当前listA和listB结点的值的大小，若值不相等，令值更小的指针后移，假如值更小的结点是listA链表中的结点，就删除该结点，并令指向listA结点的两个指针都后移一位，假如值更小的结点是listB链表中的结点，就仅移动指向listB链表中的结点，不删除结点；若值相等，就同时移动指向listA和listB链表的指针，假如listA链表比listB链表长，那么当listB链表遍历完毕时，listA链表还没有遍历完毕，但可以肯定剩下的元素都不是公共值元素，所以还需要补一个while循环用来删除listA表中剩余的结点。
    2.C语言形貌：

完整代码如下：(注意看解释)

#include <stdio.h>
#include <stdlib.h>
//Data Structure Defining
typedef struct LinkNode {
int data;
struct LinkNode * next;
} LinkNode, * LinkList;
//Functions Declaration
void initialize(LinkList * pHead);
LinkNode * createNewNode(int data);
void traverse(LinkList pHead);
void freeList(LinkList pHead);
void retainCommonValuesInListA(LinkList listA, LinkList listB);
int main(void) {
//给定两个特定的升序链表，用于测试该算法。
LinkList listA,listB;
initialize(&listA);
initialize(&listB);
LinkNode * a1 = createNewNode(2);
LinkNode * a2 = createNewNode(3);
LinkNode * a3 = createNewNode(3);
LinkNode * a4 = createNewNode(4);
LinkNode * a5 = createNewNode(777);
listA->next = a1;
a1->next = a2;
a2->next = a3;
a3->next = a4;
a4->next = a5;
a5->next = NULL;
LinkNode * b1 = createNewNode(1);
LinkNode * b2 = createNewNode(3);
LinkNode * b3 = createNewNode(4);
LinkNode * b4 = createNewNode(11);
listB->next = b1;
b1->next = b2;
b2->next = b3;
b3->next = b4;
b4->next = NULL;
printf("\n初始的升序链表listA情况: ");
traverse(listA);
printf("\n初始的升序链表listB情况: ");
traverse(listB);
retainCommonValuesInListA(listA, listB);
printf("\n最终的listA 链表情况: ");
traverse(listA);
freeList(listA);
freeList(listB);
return 0;
}
void initialize(LinkList * pHead) {
(*pHead) = (LinkNode * ) malloc(sizeof(LinkNode));
(*pHead)->data = 0;
(*pHead)->next = NULL;
}
LinkNode * createNewNode(int data) {
LinkNode * p = (LinkNode * ) malloc(sizeof(LinkNode));
p->data = data;
p->next = NULL;
return p;
}
void traverse(LinkList pHead) {
LinkNode * p = pHead->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void freeList(LinkList pHead) {
LinkNode * p = pHead;
LinkNode * temp;
while (p != NULL) {
temp = p;
p = p->next;
free(temp);
}
}
void retainCommonValuesInListA(LinkList listA, LinkList listB) {
LinkNode * prevA = listA;
LinkNode * currentA = listA->next;
LinkNode * currentB = listB->next;
while (currentA != NULL && currentB != NULL) {
if (currentA->data < currentB->data) {
prevA->next = currentA->next;
free(currentA);
currentA = prevA->next;
} else if (currentA->data > currentB->data) {
currentB = currentB->next;
} else {
//(Eliminates consecutive duplicates in the result list)
if (currentA->data == prevA->data) {
prevA->next = currentA->next;
free(currentA);
currentA = prevA->next;
}
prevA = currentA;
currentA = currentA->next;
currentB = currentB->next;
}
}
while (currentA != NULL) {
prevA->next = currentA->next;
free(currentA);
currentA = prevA->next;
}
}

复制代码

运行结果 :

3.算法的时间和空间复杂度：

   (1) 时间复杂度 :
          The time complexity is O(n + m), where n and m are the lengths of listA and listB respectively. This is optimal for this problem.
    (2) 空间复杂度：
          The space complexity is O(1) as it operates in-place on listA.

四、判定一个链表是否为另一个链表的连续子序列

0.题目：

   现有两个带有头结点的单链表listA和listB，要求判定listB是否为listA链表的一个连续子序列。
          请设计一个算法来实现上述操作，用C语言形貌该算法，而且盘算出该算法的时间复杂度和空间复杂度。
    1.算法设计思想：

“暴力法”，分别用currentA和currentB两个指针指向listA和listB的当前结点，另设指针prevA记载每一轮循环的currentA是从哪个结点开始遍历的，
listA和listB均重新开始遍历，判定当前对应的结点是否相等（指值相等），
对于第一次判定，假如不相等，令currentA指针后移一位（此时currentB指针仍然指向listB链表的首结点），重新开始判定；假如相等，就令currentA和currentB指针同时向右移，并再次判定新指向的对应的结点是否相等，
假如再次判定的结果不相等，阐明之前判定相等的结点到这儿就卡住了，形不成同listB一样的连续序列，也就是说此次循环中，cuttentA从prevA记载的位置开始遍历listA是找不到和B一样的连续序列的（注意此时currentB指针已经发生了移动），
那么，出现失败的情况后，对于listA，令currentA指向prevA记载结点的下一个结点，并令currentB的指针重新回到listB的首结点，开始新的一轮循环，
假如发现任意一方的指针指向NULL时，跳出循环，此时判定currentB是否为NULL，只要currentB为NULL，阐明肯定在listA中找到了一个与listB相同的连续子序列。

2.C语言形貌：

完整代码如下：(注意看解释)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//Data Structure Defining
typedef struct LinkNode {
int data;
struct LinkNode * next;
} LinkNode, * LinkList;
//Functions Declaration
void initialize(LinkList * pHead);
LinkNode * createNewNode(int data);
void traverse(LinkList pHead);
void freeList(LinkList pHead);
bool judgeSequentialSub(LinkList listA, LinkList listB);
int main(void) {
//Test our algorithm
LinkList listA,listB;
initialize(&listA);
initialize(&listB);
LinkNode * a1 = createNewNode(11);
LinkNode * a2 = createNewNode(2);
LinkNode * a3 = createNewNode(3);
LinkNode * a4 = createNewNode(4);
LinkNode * a5 = createNewNode(5);
listA->next = a1;
a1->next = a2;
a2->next = a3;
a3->next = a4;
a4->next = a5;
a5->next = NULL;
LinkNode * b1 = createNewNode(3);
LinkNode * b2 = createNewNode(4);
LinkNode * b3 = createNewNode(5);
listB->next = b1;
b1->next = b2;
b2->next = b3;
b3->next = NULL;
printf("\n初始的listA情况: ");
traverse(listA);
printf("\n初始的listB情况: ");
traverse(listB);
bool result = judgeSequentialSub(listA, listB);
printf("Is listB a suqential sublist from listA? %s ", result ? "Yes!" : "No!");
freeList(listA);
freeList(listB);
return 0;
}
void initialize(LinkList * pHead) {
(*pHead) = (LinkNode * ) malloc(sizeof(LinkNode));
(*pHead)->data = 0;
(*pHead)->next = NULL;
}
LinkNode * createNewNode(int data) {
LinkNode * p = (LinkNode * ) malloc(sizeof(LinkNode));
p->data = data;
p->next = NULL;
return p;
}
void traverse(LinkList pHead) {
LinkNode * p = pHead->next; //Side note: Remember the type of next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void freeList(LinkList pHead) {
LinkNode * p = pHead;
LinkNode * temp;
while (p != NULL) {
temp = p;
p = p->next;
free(temp);
}
}
bool judgeSequentialSub(LinkList listA, LinkList listB) {
LinkNode * currentA = listA->next;
LinkNode * lastTimeA = currentA; //To record where the currentA begins its traversing
LinkNode * currentB = listB->next;
while (currentA != NULL && currentB != NULL) {
if (currentA->data == currentB->data) {
currentA = currentA->next;
currentB = currentB->next;
} else { //Update the currentA and lastTimeA if it doesn't match
currentA = lastTimeA->next;
lastTimeA = currentA;
if (listB->next != currentB) { //If listB didn't move, we won't reset it.
currentB = listB->next;
}
}
}
//return (currentB == NULL) ? true : false;
return currentB == NULL;
}

复制代码

运行结果 :

3.算法的时间和空间复杂度：

   (1) 时间复杂度 :
          In the worst case scenario:
          You might need to check every node in listA as a potential starting point for a match.
          For each starting point, you might need to compare with all nodes in listB.
    So the time complexity is O(n * m) , where n is the number of nodes in listA and m is the number of nodes in listB.
    (2) 空间复杂度：
          Uses only a fixed number of additional pointers (currentA, lastTimeA, currentB) regardless of the input size.
          It doesn't use any additional data structures that grow with the input size.
          Therefore, the space complexity is O(1) - constant space.

五、判定一个循环双链表是否对称

0.题目：

   有一个带有头结点的循环双链表，判定其是否为对称的链表（讨论对称不包罗头结点）。
          请设计一个算法来实现上述操作，用C语言形貌该算法，而且盘算出该算法的时间复杂度和空间复杂度。
    1.算法设计思想：

   注意，此题与之前所有的题目都不同——此题的操尴尬刁难象是双链表，而且是循环双链表，这意味着我们需要去重新界说新的数据结构，以及新的用于链表初始化的方法，和用于遍历链表，开释链表内存的方法。
    关于链表是否对称，其实就是从链表的两端开始，每一对对应的结点的值都相同，不难想到会出现链表个数为奇数和链表个数为偶数这两种情况（一样平常讨论链表结点数时，不考虑头结点，因为头结点并不承载有效数据），利用两个指针left 和 right分别初始化为链表的尾结点和首结点，left指针以尾结点到首结点方向从右向左遍历，right指针则从首结点开始，依次向右遍历，只要left和right指向的结点的数据域相同，就继续遍历下去。
    奇数个结点和偶数个结点的差异，体如今遍历什么时候结束。对于奇数个结点的循环双链表，假如left和right即将指向的下一个结点是同一个结点，阐明之前遍历过的对应结点都是data域相同的，到这里就该结束了；对于偶数个结点的循环双链表，假如left指向的下一个结点是right当前指向的结点，大概假如right指向的下一个结点是left当前指向的结点，阐明遍历到这里也该结束了，这是一个对称的链表。反之，只要在遍历过程中发现有任何一对结点的值不对应相等，阐明这不是一个对称的链表，直接return就可以了。
    2.C语言形貌：

完整代码如下：(注意看解释)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//Data Structure Defining
typedef struct DlinkNode {
int data;
struct DlinkNode * prev, * next;
} DlinkNode, * DlinkList;
//Functions Declaration
void initialize(DlinkList * pHead);
DlinkNode * createNewNode(int data);
void traverse(DlinkList pHead);
void freeList(DlinkList pHead);
bool judgeDoubleLink(DlinkList pHead);
int main(void) {
//Here is one specific circular double linked list ,to test our algorithm
DlinkList pHead;
initialize(&pHead);
DlinkNode * d1 = createNewNode(11);
DlinkNode * d2 = createNewNode(5);
DlinkNode * d3 = createNewNode(9);
DlinkNode * d4 = createNewNode(5);
DlinkNode * d5 = createNewNode(11);
pHead->next = d1;
d1->prev = pHead;
d1->next = d2;
d2->prev = d1;
d2->next = d3;
d3->prev = d2;
d3->next = d4;
d4->prev = d3;
d4->next = d5;
d5->prev = d4;
d5->next = pHead;
pHead->prev = d5;
printf("\nLet take a look of our tentative list: ");
traverse(pHead);
bool key = judgeDoubleLink(pHead);
printf("Is it a symmetic list? %s", key ? "Yes!" : "No!");
freeList(pHead);
return 0;
}
void initialize(DlinkList * pHead) {
(*pHead) = (DlinkNode * ) malloc(sizeof(DlinkNode));
(*pHead)->data = 0;
(*pHead)->prev = NULL;
(*pHead)->next = NULL;
}
DlinkNode * createNewNode(int data) {
DlinkNode * p = (DlinkNode * ) malloc(sizeof(DlinkNode));
p->data = data;
p->prev = NULL;
p->next = NULL;
return p;
}
void traverse(DlinkList pHead) { //Don't forget it's a circular linked list
DlinkNode * p = pHead->next;
while (p != pHead) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void freeList(DlinkList pHead) { //Don't forget it's a circular linked list
DlinkNode * p = pHead;
DlinkNode * temp;
while (p->next != pHead) {
temp = p;
p = p->next;
free(temp);
}
free(pHead);
}
bool judgeDoubleLink(DlinkList pHead) {
if (pHead->next == pHead) return true;// Handle empty lists
DlinkNode * left = pHead->prev;
DlinkNode * right = pHead->next;
while (left->data == right->data) {
if (left->prev == right->next) //When the number of list is odd, take this handling
return true;
if (left->prev == right || right->next == left) //When the number of list is even, take this handling
return true;
left = left->prev;
right = right->next;
}
return false;
}

复制代码

运行结果 :

3.算法的时间和空间复杂度：

   (1) 时间复杂度 :
          The time complexity is O(n/2), which simplifies to O(n), where n is the number of nodes in the list.
    (2) 空间复杂度：
          Therefore, the space complexity is O(1) (constant space).

六、两个循环单链表的连接 (链接)

0.题目：

   给出两个均带有头结点的循环单链表，链表头指针分别为pHeadA and pHeadB，请设法将链表pHeadB链接到链表pHeadA的后面，要求得到的新链表仍然保持循环的特性。
          请设计一个算法来实现上述操作，用C语言形貌该算法，而且盘算出该算法的时间复杂度和空间复杂度。
    1.算法设计思想：

   这个没啥可讲的吧，就和链表结点的尾插类似，只不外如今是要插一个链表，把指针看清晰别瞎几把指就行。
    对了，这个题和上一个题又不一样，这个题的操尴尬刁难象是循环单链表，这意味着我们得在之前单链表界说好的数据结构和相关函数的底子上，做一些改动，比方说遍历链表的函数，以及开释链表内存的函数。
    2.C语言形貌：

完整代码如下：(注意看解释)

#include <stdio.h>
#include <stdlib.h>
//Data Strcture Defining
typedef struct LinkNode {
int data;
struct LinkNode * next;
} LinkNode, * LinkList;
//Functions Declaration
void initialize(LinkList * pHead);
LinkNode * createNewNode(int data);
void traverse(LinkList pHead);
void freeList(LinkList pHead);
void insertList(LinkList listA, LinkList listB);
int main(void) {
//Test our algorithm
LinkList listA,listB;
initialize(&listA);
initialize(&listB);
LinkNode * a1 = createNewNode(1);
LinkNode * a2 = createNewNode(2);
LinkNode * a3 = createNewNode(3);
LinkNode * a4 = createNewNode(4);
LinkNode * a5 = createNewNode(5);
listA->next = a1;
a1->next = a2;
a2->next = a3;
a3->next = a4;
a4->next = a5;
a5->next = listA;
LinkNode * b1 = createNewNode(11);
LinkNode * b2 = createNewNode(12);
LinkNode * b3 = createNewNode(13);
listB->next = b1;
b1->next = b2;
b2->next = b3;
b3->next = listB;
printf("What's the content of original listA : ");
traverse(listA);
printf("What's the content of original listB : ");
traverse(listB);
insertList(listA, listB);
printf("After insersion, FINAL listA : ");
traverse(listA);
freeList(listA);
free(listB);
return 0;
}
void initialize(LinkList * pHead) { //No distinction with the uncircular linked list
(*pHead) = (LinkNode * ) malloc(sizeof(LinkNode));
(*pHead)->data = 0;
(*pHead)->next = NULL;
}
LinkNode * createNewNode(int data) { //No distinction with the uncircular linked list
LinkNode * p = (LinkNode * ) malloc(sizeof(LinkNode));
p->data = data;
p->next = NULL;
return p;
}
void traverse(LinkList pHead) { //DIFFERENCE no.1
LinkNode * p = pHead->next;
while (p != pHead) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void freeList(LinkList pHead) { //DIFFERENCE no.2
LinkNode * p = pHead->next;
LinkNode * temp;
while (p != pHead) {
temp = p;
p = p->next;
free(temp);
}
free(pHead);
}
void insertList(LinkList listA, LinkList listB) {
LinkNode * p = listA;
LinkNode * rearA; //point to the end of listA
LinkNode * rearB; //point to the end of listB
while (p->next != listA) { //To find the rear of listA to faciliate our insersion
p = p->next;
}
rearA = p;
rearA->next = listB->next;
while (p->next != listB) {
p = p->next;
}
rearB = p;
rearB->next = listA;
}

复制代码

运行结果 :

3.算法的时间和空间复杂度：

   (1) 时间复杂度 :
          The total time complexity is O(n + m).
    (2) 空间复杂度：
          Space Complexity of insertList: O(1).

七、循环单链表反复找到最小值结点并删除

0.题目：

   已知一个带有头结点的循环单链表，要求不断地找出链表中的最小值结点，把最小值结点的值打印出来而且删除该结点，直到该链表一个有效结点不剩，最后再删除头结点。
          请设计一个算法来实现上述操作，用C语言形貌该算法，而且盘算出该算法的时间复杂度和空间复杂度。
    1.算法设计思想：

   在“C—408《数据结构》算法题底子篇—链表（上）”一文中，也就是链表专题的上篇，有一道题目是删除链表的最小值结点，其时up已经较为具体地先容了删除最小值结点需要的两个操作“找”和“删”，这里就不再赘述，假如有对思绪大概相关代码有不懂的朋友们可以点击链接再去回顾一下（就在第二道题）；
          而此题相当于之前那道题的升级版，主要差异在了两个地方——①本题操作的链表是循环链表；②本题并不是只删除一个最小值结点，而是要逐个击破，赶尽杀绝（bushi，所以up重点说一下如何处置惩罚这两个问题：针对第一个差异，只需要注意循环链表的判空条件与非循环链表不同即可；针对第二个差异，只需要在之前那道题的底子上再套一层循环即可。
    2.C语言形貌：

完整代码如下：(注意看解释)

#include <stdio.h>
#include <stdlib.h>
//Data Strcture Defining
typedef struct LinkNode {
int data;
struct LinkNode * next;
} LinkNode, * LinkList;
//Functions Declaration
void initialize(LinkList * pHead);
LinkNode * createNewNode(int data);
void traverse(LinkList pHead);
void freeList(LinkList pHead);
void continuouslyDetectMinimum(LinkList pHead);
int main(void) {
//A specific circular linked list to test our algorithm
LinkList pHead = NULL;
initialize(&pHead);
LinkNode * a1 = createNewNode(11);
LinkNode * a2 = createNewNode(14);
LinkNode * a3 = createNewNode(141);
LinkNode * a4 = createNewNode(5);
LinkNode * a5 = createNewNode(100);
pHead->next = a1;
a1->next = a2;
a2->next = a3;
a3->next = a4;
a4->next = a5;
a5->next = pHead;
printf("初始链表情况如下——\n");
traverse(pHead);
printf("挨个删除链表的最小值结点，删除次序分别如下：\n");
continuouslyDetectMinimum(pHead);
freeList(pHead);
return 0;
}
void initialize(LinkList * pHead) {
(*pHead) = (LinkNode * ) malloc(sizeof(LinkNode));
(*pHead)->data = 0;
(*pHead)->next = NULL;
}
LinkNode * createNewNode(int data) {
LinkNode * p = (LinkNode * ) malloc(sizeof(LinkNode));
p->data = data;
p->next = NULL;
return p;
}
void traverse(LinkList pHead) { //DIFFERENT FROM NORMAL LINKED LIST
LinkNode * p = pHead->next;
while (p != pHead) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
void freeList(LinkList pHead) { //DIFFERENT FROM NORMAL LINKED LIST
LinkNode * p = pHead->next;
LinkNode * temp;
while (p != pHead) {
temp = p;
p = p->next;
free(temp);
}
free(pHead);
}
void continuouslyDetectMinimum(LinkList pHead) {
LinkNode * tempPre = pHead, * minPre = pHead;
LinkNode * temp = pHead->next, * min = pHead->next;
while (pHead->next != pHead) { //Don't forget that it's a circular one
while (temp != pHead) {
if (temp->data < min->data) { //move the min and minPre if condition matched
min = temp;
minPre = tempPre;
}
tempPre = temp;
temp = temp->next; //temp is used to traverse the list,so it should be updated at every loop.
}
printf("%d ", min->data); //Demand-no.1 print the current minimum node's data
minPre->next = min->next; //Demand-no.2 delete the current minimum node itself
free(min);
//updated all four pointer for the next-time operation(find and print and delete)
tempPre = pHead, minPre = pHead;
temp = pHead->next, min = pHead->next;
}
printf("\n");
}

复制代码

运行结果：

3.算法的时间和空间复杂度：

(1) 时间复杂度 :

The outer while loop runs until the list is empty, so it executes n times, where n is the initial number of nodes in the list.
For each iteration of the outer loop, the inner while loop traverses the entire remaining list to find the minimum value.
In the first iteration, it checks n nodes, in the second n-1, then n-2, and so on.
This forms an arithmetic sequence: n + (n-1) + (n-2) + ... + 2 + 1
The sum of this sequence is n(n+1)/2
Therefore, the time complexity is O(n^2)

(2) 空间复杂度：

The algorithm uses a fixed number of pointers (tempPre, minPre, temp, min) regardless of the input size.
No additional data structures are created that grow with the input size.
The space used is constant throughout the execution of the algorithm
Overall Space Complexity: O(1)

八、非循环双链表查改结点并按照结点访问频度举行排序

0.题目：

   已知一个带有头结点的非循环双向链表，该链表的每个结点都维护有四个属性——①pev(指向当前结点的前驱结点)；②data(当前结点的有效值)；③freq(当前结点的访问频度，初始值为0)；④next(指向当前结点的后继结点)。现界说一个Locate(pHead, data)操作，该操作会访问链表中元素值为data的结点，并将该结点的freq域的值加一，同时，还会令当前链表结点保持freq域递减的次序举行分列，而且，当两个结点的freq域的值相同时，要求最近被访问的结点优先排在前面，以便使得频繁访问的结点总是更靠近链表头。要求界说一个函数实现上述Locate(pHead, data)操作，而且返回目的结点的指针。(假设给定的链表已经按照freq降序排序)
          请设计一个算法来实现上述操作，用C语言形貌该算法，而且盘算出该算法的时间复杂度和空间复杂度。
    1.算法设计思想：

   先对题干举行分解，可知该算法共需要完成五个步骤—①查找链表中指定值的结点；②修改该结点的值；③取出该结点（涉及到双链表中结点的删除）；④查找到第一个freq域比该结点大的结点；⑤将该结点插入到第一个freq域比该结点大的结点的后面（涉及到双链表中结点的插入）。
    这五个操作都很底子，因此这是一道综合题，但算不上难题，每个操作本身都没难度，注意双链表结点的删除和插入时，指针给指对就行，别瞎

		自动登录	找回密码
密码			立即注册

C 408—《数据结构》算法题底子篇—链表（下）

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云