2.7.2 答案解析
一、单项选择题
1、B。主要考查链表的优缺点。
2、A。主要考查链表的插入操作。如图2-33所示。
图2-33 链表的插入
3、A。主要考查循环单链表的特点。
4、C。主要考查双向链表的插入操作，如图2-34所示。在双向链表中插入新结点时，需要注意修改指针的先后顺序。①q->prior=p;②q->next=p->next;③p->next->prior=q;④p->next=q;，其中①和②的顺序可以相互调换，③和④不能位于①和②之前，③和④的顺序不能颠倒。正确的执行步骤可以是①②③④或②①③④。
图2-34 双向链表的插入
5、C。链表中的元素存储地址可以是连续的，也可以是不连续的，即不一定是连续的。
6、D。
7、C。
8、C。
9、A。
10、D。
11、A。
12、C。
13、C。
14、A。
15、A。
16、A。
17、B。
18、D。
19、D。分析：需要考虑到链表为空和长度为2两种情况。
20、D。分析：对于链表来说，时间耗费主要在两个元素的比较上，假设链表的长度记作：a=min（m，n），b=max（m，n），第一个链表的长度小于第二个链表的长度，即a<b。两个表均为升序排列，依次将第一个链表的元素a1和第二个链表的元素b1进行比较，若a1<b1，则利用头插法将a1插入新链表c中，然后比较a2和b1，以此类推，直至将所有元素都插入到c中。
最好情况是第一个链表中的元素都排在第二个链表元素之前，即第一个链表中的最大的元素值比第二个链表中最大的元素值还小，此时时间复杂度为O（min（m，n））。
最坏情况是两个链表的元素值大小相间，这就需要将两个表中的所有元素比较完毕，此时最多比较次数为m+n-1，时间复杂度为O（m+n-1），接近答案O（max（m，n））。
二、综合分析题
1、（1）p=p->next
（2）p->data
2、（1）s->next=p->next
（2）p->next=s
3、（1）p->next!=NULL或p->next
（2）p->next=q->next
4、求链表的长度，即元素的个数。
5、（1）p!=h
（2）p->exp!=0
（3）=p->coef*p->exp或*=p->exp
（4）--或=p->exp-1
（5）p
（6）q->next=p->next
（7）q或h
（8）p=p->next
6、（1）L->next=NULL
（2）p!=NULL或p
（3）q!=NULL或q
（4）p->next=r->next或p->next=q
（5）r->next=p
三、算法设计题
1、分析：在将链表逆置时，仍然使用原链表的结点空间。初始时，逆置的链表为空，先将头结点的next域置为空。然后利用p指向原链表的下一个结点，q指向待插入的结点，将q指向的结点插入到链表头部（头插法建表），从而实现将链表中结点逆置。
2、分析：设L1和L2的头指针分别为head1和head2。令p和q分别指向第一个和第二个链表的最后一个结点，修改第一个链表的最后一个结点的指针域，使其指向第二个链表的第一个结点，然后修改第二个链表的最后一个结点指针域，使其指向第一个链表的头结点。
3、分析：L指向有序链表，p指向待排序链表。初始时，令L->next=NULL，即有序链表为空。若有序链表为空，则将p指向的结点直接插入到空链表中。然后将p指向的第二个结点与L所指链表中的每一个结点比较，并将结点*p插入到L所指链表的相应位置，使其按有序排列。重复执行以上操作，直至待排序链表中所有结点都插入到L指向的链表。此时，L就成为一个有序链表。
4、分析：依次分别扫描两个链表中的每个结点，对于A中的结点元素，若在B中也存在与该元素值相同的结点，则将该结点插入到C中。
5、分析：为了实现A-B的操作，先将两个链表分别进行从小到大排序，然后依次比较两个链表中的元素，在A中出现的元素，若在B中也出现，则将A中的元素删除。在执行A-B操作之前，先增加一个头结点，以便插入方便；在插入完成后，再将头结点释放。
6、分析：此题为单链表合并问题。利用尾插法建立单链表，使先插入元素值小的结点在链表表头，后插入元素值大的结点在链表表尾。初始时，单链表C为空（插入的是C的第一个结点），将单链表A和B中较小的元素值结点插入到C中；单链表C不为空时，比较C和将插入结点的元素值大小，值不同时插入到C中，值相同时，释放该结点。当A和B中有一个链表为空时，将剩下的结点依次插入到C中。
7、分析：可以使用原有结点空间而不建立新结点来合并双向循环链表。首先以A的头结点建立新的空双向链表；分别用指针p和q指向链表A和B的第一个结点，依次比较p和q指示的结点元素大小，取下较小的结点作为新链表的结点，插入到新链表的表尾，重复这一过程一直至A和B中有一个链表为空；如果A和B中有一个链表为空而另一个链表不为空时，将不空的链表剩下的部分插入新链表的表尾。
8、分析：该题与第1题单链表的逆置方法相同。
9、分析：找到最后一个0，将该二进制位上的0变为1，其后1全变为0。如果未找到0，则表示为全1，将全部的二进制1变为0，最后用头插法在最前面插入一个1。
10、分析：令指针p和q分别指向str1和str2，扫描两个链表，当p和q指向同一个地址时，即找到共同后缀的起始位置。设str1和str2指向的链表长度分别为a和b。令指针p和q分别指向str1和str2的头结点，若a≥b，则指针p先扫描，使p指向链表的第（a−b+1）个结点；若a＜b，则让q先扫描str2，使q指向链表中的第（b−a+1）个结点，即令指针p和q所指向的结点到表尾的长度相等，将两个链表以表尾对齐。反复让指针p和q同步向后移动，当p和q指向同一个位置时停止，即为共同后缀的起始地址。
11、分析：通过观察前后链表结点顺序的变化，L’是通过选取L中的第一个结点、最后一个结点、第二个结点、倒数第二个结点…组成的。为了方便取得链表中的后半段结点，可将链表L的后半段逆置。为了逆置链表的后半段，需要找到后半段链表的起始位置。设置两个指针变量p和m，当未到达链表末尾时，使p往前走两步，m走一步，当p为空的时候，m就指向了链表的中间位置。这个思路类似于全国统考2009年求链表中倒数第k个结点的思路。
然后将m指向的链表后半段逆置，然后分别选取两个链表的第1~n/2个元素，形成新的链表。
时间主要耗费在第一个while循环的查找链表后半段的操作、逆置后半段链表和将结点插入的操作过程中，期时间复杂度均为O（n），故总的时间复杂度为O（n）。
12、分析：算法思想与第6题类似，有两种方法：（1）将链表B逆置后，依次比较A和B中的元素，将较小的插入到链表C中；（2）不逆置链表B，依次比较A和B中的元素，将较小的元素插入到C中，直至其中一个链表为空，此时若链表A不为空，则直接把A中剩下的结点直接链接到C的最后即可；若链表B不为空，因为B是按元素值递减排列的，所以需要依次取出B中剩下的元素结点，逐个以头插法插入到C的后面。
