02. 【解答】
## 02. 【解答】 算法思想：用 p 从头至尾扫描单链表，pre 指向 *p 结点的前驱，用 minp 保存值最小的结点指针（初值为 p），minpre 指向 *minp 结点的前驱（初值为 pre）。一边扫描，一边比较，若 p->data 小于 minp->data，则将 p、pre 分别赋值给 minp、minpre，如下图所示。当 p 扫描完毕时，minp 指向最小值结点，minpre 指向最小值结点的前驱结点，再将 minp 所指结点删除即可。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 63 --> 第2章 线性表 51 本题代码如下：算法需要从头至尾扫描链表，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 若本题改为不带头结点的单链表，则实现上会有所不同，请读者自行思考。 ## 03. 【解答】 解法1：将头结点摘下，然后从第一结点开始，依次插入到头结点的后面（头插法建立单链表），直到最后一个结点为止，这样就实现了链表的逆置，如下图所示。LinkList Delete_Min(LinkList &amp;L) { LNode *pre=L, *p=pre-&gt;next; //p 为工作指针，pre 指向其前驱 LNode *minpre=pre, *minp=p; //保存最小值结点及其前驱 while (p != NULL) { if (p-&gt;data &lt; minp-&gt;data) { minp=p; //找到比之前找到的最小值结点更小的结点 minpre=pre; } pre=p; //继续扫描下一个结点 p=p-&gt;next; } minpre-&gt;next=minp-&gt;next; //删除最小值结点 free(minp); return L; }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
本题代码如下： 解法2：大部分辅导书都只介绍解法1，这对读者的理解和思维是不利的。为了将调整指针这个复杂的过程分析清楚，我们借助图形来进行直观的分析。 假设pre、p和r指向三个相邻的结点，如下图所示。假设经过若干操作后，*pre之前的结点的指针都已调整完毕，它们的next都指向其原前驱结点。现在令*p结点的next域指向*pre结点，注意到一旦调整指针的指向，*p的后继结点的链就会断开，为此需要用r来指向原*p的后继结点。处理时需要注意两点：一是在处理第一个结点时，应将其next域置为NULL，而不是指向头结点（因为它将作为新表的尾结点）；二是在处理完最后一个结点后，需要将头结点的指针指向它。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 64 --> 2027年数据结构考研复习指导 本题代码如下：上述两个算法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 ## 04. 【解答】 因为链表是无序的，所以只能逐个结点进行检查，执行删除。 本题代码如下：LinkList Reverse_2(LinkList L) { LNode *pre, *p=L-&gt;next, *r=p-&gt;next; p-&gt;next=NULL; //处理第一个结点 while (r!=NULL) { //r 为空，则说明 p 为最后一个结点 pre=p; //依次继续遍历 p=r; r=r-&gt;next; p-&gt;next=pre; //指针反转 L-&gt;next=p; //处理最后一个结点 return L; }## 05. 【解答】 两个单链表有公共结点，即两个链表从某一结点开始，它们的 next 都指向同一结点。每个单链表结点只有一个 next 域，因此从第一个公共结点开始，之后的所有结点都是重合的，不可能再出现分叉。所以两个有公共结点而部分重合的单链表，拓扑形状看起来像 Y，而不可能像 X。 本题极容易联想到“蛮”方法：在第一个链表上顺序遍历每个结点，每遍历一个结点，在第二个链表上顺序遍历所有结点，若找到两个相同的结点，则找到了它们的公共结点。显然，该算法的时间复杂度为 $O(\mathrm{len1} \cdot \mathrm{len2})$。 接下来我们试着去寻找一个线性时间复杂度的算法。先把问题简化：如何判断两个单链表有没有公共结点？应注意到这样一个事实：若两个链表有一个公共结点，则该公共结点之后的所有结点都是重合的，即它们的最后一个结点必然是重合的。因此，我们判断两个链表是不是有重合的部分时，只需要分别遍历两个链表到最后一个结点。若两个尾结点是一样的，则说明它们有公共结点，否则两个链表没有公共结点。 然而，在上面的思路中，顺序遍历两个链表到尾结点时，并不能保证在两个链表上同时到达尾结点。这是因为两个链表长度不一定一样。但假设一个链表比另一个长 $k$ 个结点，我们先在长的链表上遍历 $k$ 个结点，之后再同步遍历，此时我们就能保证同时到达最后一个结点。两个链表从第一个公共结点开始到链表的尾结点，这一部分是重合的，因此它们肯定也是同时到达第一公共结点的。于是在遍历中，第一个相同的结点就是第一个公共的结点。 根据这一思路中，我们先要分别遍历两个链表得到它们的长度，并求出两个长度之差。在长 <!-- page: 65 --> 第2章 线性表 53 的链表上先遍历长度之差个结点之后，再同步遍历两个链表，直到找到相同的结点，或者一直到链表结束。此时，该方法的时间复杂度为 $O(\mathrm{len1} + \mathrm{len2})$。 ## 06. 【解答】 算法思想：循环遍历链表 C，采用尾插法将一个结点插入表 A，这个结点为奇数号结点，这样建立的表 A 与原来的结点顺序相同；采用头插法将下一结点插入表 B，这个结点为偶数号结点，这样建立的表 B 与原来的结点顺序正好相反。 本题代码如下：void RangeDelete(LinkList &amp;L,int min,int max) { LNode *pr=L,*p=L-&gt;link; //p 是检测指针，pr 是其前驱 while (p!=NULL) if (p-&gt;data&gt;min&amp;&amp;p-&gt;data&lt;max) { //寻找到被删结点，删除 pr-&gt;link=p-&gt;link; free(p); p=pr-&gt;link; } else { //否则继续寻找被删结点 pr=p; p=p-&gt;link; }要特别注意的是，该算法采用头插法插入结点后，*p 的指针域已改变，若不设变量保存其后继结点，则会引起断链，从而导致算法出错。 ## 07. 【解答】 算法思想：题中链表是有序表，因此所有相同值域的结点都是相邻的。用 p 扫描递增单链表 L，若 *p 结点的值域等于其后继结点的值域，则删除后者，否则 p 移向下一个结点。 本题代码如下：LinkList DisCreat_2(LinkList &amp;A) { LinkList B = (LinkList)malloc(sizeof(LNode)); //创建 B 表表头 B-&gt;next = NULL; //B 表的初始化 LNode *p = A-&gt;next, *q; //p 为工作指针 LNode *ra = A; //ra 始终指向 A 的尾结点 while (p != NULL) { ra-&gt;next = p; ra = p; //将 *p 链到 A 的表尾 p = p-&gt;next; if (p != NULL) { q = p-&gt;next; //头插后，*p 将断链，因此用 q 记忆 *p 的后继 p-&gt;next = B-&gt;next; //将 *p 插入到 B 的前端 B-&gt;next = p; p = q; } } ra-&gt;next = NULL; //A 尾结点的 next 域置空 return B; }本算法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 本题也可采用尾插法，将头结点摘下，然后从第一结点开始，依次与已经插入结点的链表的最后一个结点比较，若不等则直接插入，否则将当前遍历的结点删除并处理下一个结点，直到最后一个结点为止。 ## 08. 【解答】 <!-- page: 66 --> 2027年数据结构考研复习指导 算法思想：表A、B都有序，可从第一个元素起依次比较A、B两表的元素，若元素值不等，则值小的指针往后移，若元素值相等，则创建一个值等于两结点的元素值的新结点，使用尾插法插入到新的链表中，并将两个原表指针后移一位，直到其中一个链表遍历到表尾。 本题代码如下：void Del_Same(LinkList &amp;L) { LNode *p = L-&gt;next, *q; //p 为扫描工作指针 if (p == NULL) return; while (p-&gt;next != NULL) { q = p-&gt;next; //q 指向 *p 的后继结点 if (p-&gt;data == q-&gt;data) { //找到重复值的结点 p-&gt;next = q-&gt;next; //释放 *q 结点 free(q); //释放相同元素值的结点 } else p = p-&gt;next; } }## 09. 【解答】 算法思想：采用归并的思想，设置两个工作指针 $pa$ 和 $pb$，对两个链表进行归并扫描，只有同时出现在两集合中的元素才链接到结果表中且仅保留一个，其他的结点全部释放。当一个链表遍历完毕后，释放另一个表中剩下的全部结点。 本题代码如下：void Get_Common(LinkList A, LinkList B) { LNode *p=A-&gt;next, *q=B-&gt;next, *r, *s; LinkList C=(LinkList)malloc(sizeof(LNode)); //建立表C r=C; //r始终指向C的尾结点 while (p!=NULL&amp;&amp;q!=NULL) { //循环跳出条件 if (p-&gt;data<q->data) p=p-&gt;next; //若A的当前元素较小，后移指针 else if (p-&gt;data&gt;q-&gt;data) q=q-&gt;next; //若B的当前元素较小，后移指针 else { //找到公共元素结点 s=(LNode*)malloc(sizeof(LNode)); s-&gt;data=p-&gt;data; //复制产生结点*s r-&gt;next=s; //将*s链接到C上（尾插法） r=s; p=p-&gt;next; //表A和B继续向后扫描 q=q-&gt;next; } } r-&gt;next=NULL; //置C尾结点指针为空 }链表归并类型的试题在各学校历年真题中出现的频率很高，故应扎实掌握解决此类问题的思想。该算法的时间复杂度为 $O(\mathrm{len}1 + \mathrm{len}2)$，空间复杂度为 $O(1)$。 ## 10. 【解答】 算法思想：因为两个整数序列已存入两个链表中，操作从两个链表的第一个结点开始，若对应数据相等，则后移指针；若对应数据不等，则 A 链表从上次开始比较结点的后继开始，B 链表仍从第一个结点开始比较，直到 B 链表到尾表示匹配成功。A 链表到尾而 B 链表未到尾表示失败。操作中应记住 A 链表每次的开始结点，以便下次匹配时好从其后继开始。 本题代码如下：LinkList Union(LinkList &amp;la, LinkList &amp;lb) { LNode *pa=la-&gt;next; //设工作指针分别为 pa 和 pb LNode *pb=lb-&gt;next; LNode *u, *pc=la; //结果表中当前合并结点的前驱指针 pc while (pa&amp;&amp;pb) { if (pa-&gt;data==pb-&gt;data) { //交集并入结果表中 pc-&gt;next=pa; //A中结点链接到结果表 pc=pa; pa=pa-&gt;next; u=pb; //B中结点释放 pb=pb-&gt;next; free(u); } else if (pa-&gt;data&lt;pb-&gt;data) { //若A中当前结点值小于B中当前结点值 u=pa; pa=pa-&gt;next; //后移指针 free(u); //释放A中当前结点 } else { //若B中当前结点值小于A中当前结点值 u=pb; pb=pb-&gt;next; //后移指针 free(u); //释放B中当前结点 } } //while 结束</q-> <!-- page: 67 --> 第2章 线性表 55 ```txt while(pa) { //B 已遍历完，A 未完 u=pa; pa=pa-&gt;next; free(u); //释放 A 中剩余结点 } while(pb) { //A 已遍历完，B 未完 u=pb; pb=pb-&gt;next; free(u); //释放 B 中剩余结点 } pc-&gt;next=NULL; //置结果链表尾指针为 NULL free(lb); //释放 B 表的头结点 return la;## 注意 该题其实是字符串模式匹配的链式表示形式，读者应该结合字符串模式匹配的内容重新考虑能否优化该算法。 ## 11. 【解答】 算法思想：让 p 从左向右扫描，q 从右向左扫描，直到它们指向同一结点（p==q，当循环双链表中结点个数为奇数时）或相邻（p->next=q 或 q->prior=p，当循环双链表中结点个数为偶数时）为止，若它们所指结点值相同，则继续进行下去，否则返回 0。若比较全部相等，则返回 1。 本题代码如下： <!-- page: 68 --> 2027年数据结构考研复习指导int Pattern(LinkList A, LinkList B) { LNode *p=A; //p 为 A 链表的工作指针，本题假定 A 和 B 均无头结点 LNode *pre=p; //pre 记住每趟比较中 A 链表的开始结点 LNode *q=B; //q 是 B 链表的工作指针 while(p&amp;&amp;q) if(p-&gt;data==q-&gt;data) { //结点值相同 p=p-&gt;next; q=q-&gt;next; } else{ pre=pre-&gt;next; p=pre; //A 链表新的开始比较结点 q=B; //q 从 B 链表第一个结点开始 } if(q==NULL) //B 已经比较结束 return 1; //说明 B 是 A 的子序列 else return 0; //B 不是 A 的子序列 }**注意** ## 12. 【解答】 算法思想：先找到两个链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来，再使之成为循环的。 本题代码如下：int Symmetry(DLinkList L) { DNode *p=L-&gt;next, *q=L-&gt;prior; //两头工作指针 while (p!=q&amp;&amp;p-&gt;next!=q) //循环跳出条件 if (p-&gt;data==q-&gt;data) { //所指结点值相同则继续比较 p=p-&gt;next; q=q-&gt;prior; } else //否则，返回 0 return 0; return 1; //比较结束后返回 1 }## 13. 【解答】 算法思想：首先在双链表中查找数据值为 x 的结点，查到后，将结点从链表上摘下，然后顺着结点的前驱链查找该结点的插入位置（频度递减，且排在同频度的第一个，即向前找到第一个比它的频度大的结点，插入位置为该结点之后），并插入到该位置。 本题代码如下：LinkList Link(LinkList &amp;h1, LinkList &amp;h2) { //将循环链表 h2 链接到循环链表 h1 之后，使之仍保持循环链表的形式 LNode *p, *q; //分别指向两个链表的尾结点 p=hl; while (p-&gt;next!=hl) //寻找 h1 的尾结点 p=p-&gt;next; q=h2; while (q-&gt;next!=h2) //寻找 h2 的尾结点 q=q-&gt;next; p-&gt;next=h2; //将 h2 链接到 h1 之后 q-&gt;next=hl; //令 h2 的尾结点指向 h1 return h1; }## 14. 【解答】 ### 1）算法的基本设计思想： 首先，遍历链表计算表长 $n$，并找到链表的尾结点，将其与首结点相连，得到一个循环单链表。然后，找到新链表的尾结点，它为原链表的第 $n-k$ 个结点，令 $L$ 指向新链表尾结点的下一个结点，并将环断开，得到新链表。 ### 2）本题代码如下：DLinkList Locate(DLinkList &amp;L, ElemType x) { DNode *p=L-&gt;next, *q; //p 为工作指针，q 为 p 的前驱，用于查找插入位置 while (p&amp;&amp;p-&gt;data!=x) p=p-&gt;next; //查找值为 x 的结点 if (!p) exit(0); //不存在值为 x 的结点 else{ p-&gt;freq++; //令元素值为 x 的结点的 freq 域加 1 if (p-&gt;pre==L || p-&gt;pre-&gt;freq &gt; p-&gt;freq) return p; //p 是链表首结点，或 freq 值小于前驱 if (p-&gt;next!=NULL) p-&gt;next-&gt;pre=p-&gt;pre; p-&gt;pre-&gt;next=p-&gt;next; //将 p 结点从链表上摘下 q=p-&gt;pre; //以下查找 p 结点的插入位置 while (q!=L&amp;&amp;q-&gt;freq&lt;=p-&gt;freq) q=q-&gt;pre; p-&gt;next=q-&gt;next; } <!-- page: 69 --> 第2章 线性表 57 ```c if(q-&gt;next != NULL) q-&gt;next-&gt;pre = p; //将 p 结点排在同频率的第一个 p-&gt;pre = q; q-&gt;next = p; } return p; //返回值为 x 的结点的指针### 3）本算法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 ## 15. 【解答】 ### 1）算法的基本设计思想： 设置快慢两个指针分别为 fast 和 slow 最初都指向链表头 head。slow 每次走一步，即 slow=slow->next；fast 每次走两步，即 fast=fast->next->next。fast 比 slow 走得快，若有环，则 fast 一定先进入环，而 slow 后进入环。两个指针都进入环后，经过若干操作后两个指针定能在环上相遇。这样就可以判断一个链表是否有环。 如下图所示，当 slow 刚进入环时，fast 早已进入环。因为 fast 每次比 slow 多走一步且 fast 与 slow 的距离小于环的长度，所以 fast 与 slow 相遇时，slow 所走的距离不超过环的长度。LNode *Converse(LNode *L,int k){ int n=1; //n 用来保存链表的长度 LNode *p=L; //p 为工作指针 while(p-&gt;next != NULL) { //计算链表的长度 p=p-&gt;next; n++; } //循环执行后，p 指向链表尾结点 p-&gt;next=L; //将链表连成一个环 for(int i=1;i&lt;=n-k;i++) //寻找链表的第 n-k 个结点 p=p-&gt;next; L=p-&gt;next; //令 L 指向新链表尾结点的下一个结点 p-&gt;next=NULL; //将环断开 return L; }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
如下图所示，设头结点到环的入口点的距离为 $a$，环的入口点沿着环的方向到相遇点的距离为 $x$，环长为 $r$，相遇时 fast 绕过了 $n$ 圈。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 70 --> 2027年数据结构考研复习指导 则有 $2(a + x) = a + n * r + x$，即 $a = nr - x$。显然从头结点到环的入口点的距离等于 $n$ 倍的环长减去环的入口点到相遇点的距离。因此可设置两个指针，一个指向 head，另一个指向相遇点，两个指针同步移动（均为一次走一步），相遇点即环的入口点。 2）本题代码如下：3）当 fast 与 slow 相遇时，slow 肯定没有遍历完链表，故算法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。 16. 【解答】 1）算法的基本设计思想： 设置快、慢两个指针分别为 fast 和 slow，初始时 slow 指向 L（第一个结点），fast 指向 L->next（第二个结点），之后 slow 每次走一步，fast 每次走两步。当 fast 指向表尾（第 $n$ 个结点）时，slow 正好指向链表的中间点（第 $n/2$ 个结点），即 slow 正好指向链表前半部分的最后一个结点。将链表的后半部分逆置，然后设置两个指针分别指向链表前半部分和后半部分的首结点，在遍历过程中计算两个指针所指结点的元素之和，并维护最大值。 2）本题代码如下：LNode* FindLoopStart(LNode *head) { LNode *fast = head, *slow = head; //设置快慢两个指针 while (fast != NULL &amp;&amp; fast-&gt;next != NULL) { slow = slow-&gt;next; //每次走一步 fast = fast-&gt;next-&gt;next; //每次走两步 if (slow == fast) break; //相遇 } if (fast == NULL || fast-&gt;next == NULL) return NULL; //没有环，返回 NULL LNode *p1 = head, *p2 = slow; //分别指向开始点、相遇点 while (p1 != p2) { p1 = p1-&gt;next; p2 = p2-&gt;next; } return p1; //返回入口点 }3）本算法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。int PairSum(LinkList L) { LNode *fast = L-&gt;next, *slow = L; //利用快慢双指针找到链表的中间点 while (fast != NULL &amp;&amp; fast-&gt;next != NULL) { fast = fast-&gt;next-&gt;next; //快指针每次走两步 slow = slow-&gt;next; //慢指针每次走一步 } LNode *newHead = NULL, *p = slow-&gt;next, *tmp; while (p != NULL) { tmp = p-&gt;next; //p 指向当前待插入结点，令 tmp 指向其下一结点 p-&gt;next = newHead; //将 p 所指结点插入到新链表的首结点之前 newHead = p; //newHead 指向刚才新插入的结点，作为新的首结点 p = tmp; //当前待处理结点变为下一结点 } int mx = 0; p = L; LNode *q = newHead; while (q != NULL) { if ((p-&gt;data + q-&gt;data) &gt; mx) //用 mx 记录最大值 mx = p-&gt;data + q-&gt;data; p = p-&gt;next; q = q-&gt;next; } } <!-- page: 71 --> 第2章 线性表 59 ```txt return mx; }