程序员面试分类模拟7

程序员面试分类模拟7论述题1.

如何找出数组中只出现一次的数字正确答案：一个整型数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。要求时间复杂度是O(n)，空间复杂（江南博哥）度是O(1)。

如果本题对时间复杂度没有要求的话，最容易想到的方法就是首先对这个整型数组排序，然后从第一个数字开始遍历，比较相邻的两个数，从而找出这个只出现一次的数字，所以其时间复杂度最快为O(nlogn)。

由于时间复杂度与空间复杂度的限制，该种方法不可取，所以需要一种更高效的方式。题目强调只有一个数字出现一次，其他的出现了两次，首先想到的是异或运算的性质：任何一个数字异或它自己都等于0，根据这一特性，如果从头到尾依次异或数组中的每一个数字，因为那些出现两次的数字全部在异或中抵消掉了，所以最终的结果刚好是那个只出现一次的数字。

程序示例如下：

#include＜stdio.h＞

intfindNotDouble(inta[],intn)

{

intresult=a[0];

inti;

for(i=1;i＜n;++i)

result^=a[i];

returnresult;

}

intmain()

{

intarray[]={1,2,3,2,4,3,5,4,1};

intlen=sizeof(array)/sizeof(array[0]);

intnum=findNotDouble(array,len);

printf("%d\n",num);

return0;

}

程序输出结果：

5

引申：如果题目改为整型数组中除了两个数字之外，其他的数字都出现了两次，如何求解这两个只出现一次的数?

在上述解决方案的基础上，如果能够把原数组分为两个子数组，在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次，问题就可以很容易地解决了：分别对两个子数组按照上述解决方案执行结果。

现在问题的难点就是如何划分为两个符合求解方案的子数组。首先从头到尾依次异或数组中的每一个数字，因为其他数字都出现了两次，在异或中全部抵消掉了，所以最终得到的结果将是两个只出现一次的数字的异或结果。而这两个数字肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1，否则就为0了。在结果数字中找到第一个为1的位的位置，记为第N位，此时以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0。通过这种方法就可以把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。

程序示例如下：

#include＜stdio.h＞

voidfmdOnce(intdata[],intn,int&num1,int&num2)

if(n＜5)

return;

intr1=0;

for(inti=0;i＜n;i++)

r1^=data[i];

intbitNum=0;

while(!(r1&0x1))

{

r1＞＞=1;

++bitNum;

}

intflag=(1＜＜bitNum);

num1=0;

num2=0;

for(intj=0;j＜n;j++)

{

if(data[j]&flag)

num1^=data[j];

else

num2^=data[j];

}

}

intmain()

{

intarray[]={1,2,3,2,4,3,5,1};

intnum1,hum2;

findOnce(array,sizeof(array)/sizeof(array[0]),num1,num2);

printf("%d\n%d\n",num1,num2);

return0;

}

程序输出结果：

5

4

2.

如何判断一个整数x是否可以表示成n(n≥2)个连续正整数的和正确答案：假设x可以表示成n(n≥2)个连续正整数的和，那么数学表达式如下：x=m+(m+1)+(m+2)+...+(m+n-1)，其中m为分解成的连续整数中最小的那一个，由于m是大于等于1的正整数，可知x=(2m+n-1)×n/2，变换之后m=(2×x/n-n+1)/2，由m的范围可以知道(2×x/n-n+1)/2≥1，以上就是X和n的关系。给定一个n，看是否x能分解成n个连续整数的和，可以判断是否存在m，也就转换成(2×x/n-n+1)是否是偶数的问题。

判断一个数是否是偶数，是一个比较容易解决的问题，所以本题就迎刃而解了，程序示例如下：

#inchude＜stdio.h＞

#include＜math.h＞

intmain()

{

intm=0,n=0,start=0,end=0,flag=0;

floattemp=0.0;

printf("请输入被分解的数:");

scanf("%d",&m);

printf("请输入需要被分解的数字的个数:");

scanf("%d",&n);

temp=(float)m/n-(float)(n-1)/2;

if(temp==(int)temp)

{

for(flag=1,start=(int)temp,end=start+n;start＜end;start++)

printf("%d",start);

printf("\n");

}

if(flag==0)

printf("没有符合条件的个数\n");

return0;

}

程序输出结果：

请输入被分解的数：10

请输入需要被分解的数字的个数：4

1

2

3

4

3.

数组和链表的区别是什么正确答案：数组与链表是两种不同的数据存储方式。链表的特性是在中间任意位置添加元素、删除元素都非常地快，不需要移动其他的元素。通常对于单链表而言，链表中每一个元素都要保存一个指向下一个元素的指针；而对于双链表，每个元素既要保存一个指向下一个元素的指针，还要保存一个指向上一个元素的指针；循环链表则在最后一个元素中保存一个指向第一个元素的指针。

数组是一组具有相同类型和名称的变量的集合，这些变量称为数组的元素，每个数组元素都有一个编号，这个编号称为数组的下标，可以通过下标来区别并访问这些元素，数组元素的个数也称为数组的长度。

具体而言，数组和链表的区别主要表现在以下几个方面：

1)逻辑结构。数组必须事先定义固定的长度(元素个数)，不能适应数据动态地增减的情况，即在使用数组之前，就必须对数组的大小进行确定。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。数组中插入、删除数据项时，需要移动其他数据项。而链表采用动态分配内存的形式实现，可以适应数据动态地增减的情况，需要时可以用new/malloc分配内存空间，不需要时用delete/free将已分配的空间释放，不会造成内存空间浪费，且可以方便地插入、删除数据项。

2)内存结构。(静态)数组从栈中分配空间，对于程序员方便快速，但是自由度小。链表从堆中分配空间，自由度大，但是申请管理比较麻烦。

3)数组中的数据在内存中是顺序存储的，而链表是随机存储的。数组的随机访问效率很高，可以直接定位，但插入、删除操作的效率比较低。链表在插入、删除操作上相对数组有很高的效率，而如果要访问链表中的某个元素，那就得从表头逐个遍历，直到找到所需要的元素为止，所以链表的随机访问效率比数组低。

4)链表不存在越界问题，数组有越界问题。数组便于查询，链表便于插入删除，数组节省空间但是长度固定，链表虽然变长但是占了更多的存储空间。

所以，由于数组存储效率高、存储速度快的优点，如果需要频繁访问数据，很少插入删除操作，则使用数组；反之，如果频繁插入删除，则应使用链表。两者各有用处。

4.

何时选择顺序表、何时选择链表作为线性表的存储结构为宜正确答案：顺序表按照顺序存储，即数据元素存放在一个连续的存储空间之中，实现顺序存取或(按下标)直接存取。链表按照链接存储，即存储空间一般在程序的运行过程中动态分配与释放，且只要存储器中还有空间，就不会产生存储溢出的问题。

顺序表与链表各有短长，在实际应用中，应根据具体问题的要求和性质来选择使用哪一种存储结构，通常有以下几方面的考虑：

1)空间。顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大，当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。

2)时间。顺序表是随机存取结构，若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。

所以，不能笼统地说哪种实现更好，必须根据实际问题的具体需要，并对各个方面的优缺点进行综合评估，才能最终选择一种比较适合的实现方法。

5.

如何使用链表头正确答案：在回答这个问题前，首先弄清楚一个概念，什么是结点?简单地说，结点表示的就是数据域与指针域的和，数据域存储数据元素的信息，指针域指示直接后继存储位置，所以结点表示数据元素或数据元素的映像关系。

单链表的开始结点之前附设一个类型相同的结点，称之为头结点，头结点的数据域可以不存储任何信息(也可以存放如线性表的长度等附加信息)，头结点的指针域存储指向开始结点的指针(即第一个元素结点的存储位置)。如图所示为带头结点的单链表。

图1带头结点的单链表

头结点的作用主要有以下两点：

1)对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。

2)对带头结点的链表，表头指针是指向首结点的非空指针，因此空表与非空表的处理是一样的。

在实现运算时，需要动态产生出其头结点，并将其后继指针置为空。

voidinitial_List(node*L)

{

L=(node*)malloc(sizeof(node));

L-＞next=NULL;

}

需要注意的是，开始结点、头指针、头结点并不是一个概念，它们是有区别的。开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点，而链表的头指针是指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。图2所示链表的头指针为head，则称该链表为链表head，在定义链表变量时可以这样声明：node*head，而头结点是人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，无论链表是否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。

图2链表head结构

6.

如何实现单链表的插入、删除操作正确答案：插入运算是将值为x的新结点插入到单链表的第i个结点的位置上，即插入到ai-1与ai之间。具体算法如下：

1)找到ai-1存储位置p。

2)生成一个数据域为x的新结点*s。

3)令结点*p的指针域指向新结点s。

4)新结点s的指针域指向结点ai。

图3所示为单链表插入结点示意图。

图3单链表插入结点示意图

单链表插入结点具体算法实现如下：

StatusInsertList(LinkListhead,DataTypex,inti)

{

ListNode*p;

p=head;

intj=1;

while(p&&j＜i)

{

p=p-＞next;

++j;

}

if(!p)‖j＞i)

{

printf("PositionError");

retumERROR;

}

s=(ListNode*)malloc(sizeof(ListNode));

s-＞data=x;

s-＞next=p-＞next;

P-＞next=s;

returnOK;

}

单链表插入算法的时间主要耗费在查找操作GetNode，即获得结点上，故单链表插入操作的时间复杂度为O(n)。

单链表的删除操作是将单链表的第i个结点删去。其具体步骤如下：

1)找到ai-1的存储位置P(因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中)。

2)令p→next指向ai的直接后继结点(即把ai从链上摘下)ai+1。

3)释放结点ai的空间，将其归还给“存储池”。

图4所示为单链表删除结点示意图。

图4单链表删除结点示意图

单链表删除结点具体算法实现如下：

StatusDeleteList(LinkListhead,inti)

{

ListNode*p,*r;

P=head;

intj=1;

while(p-＞next&&j＜i)

{

p=p-＞next;

++j;

}

if(p-＞next==NULL‖j＞i)

{

printf("PositionError");

returnERROR;

}

r=p-＞next;

P-＞next=r-＞next;

free(r);

returnOK;

}

设单链表的长度为n，则单链表删除第i个结点时，必须保证1≤i≤n，否则不合法。而当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此，被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在(即p!=NULL)且*p不是终端结点(即p-＞next!=NULL)同时满足j≤i时，才能确定被删结点存在。此时，算法的时间复杂度也是O(n)。

引申：如何删除单链表的头元素?

要删除头元素，首先需要通过头结点定位头元素，并将头结点指向头元素的下一个元素，然后释放头元素的内存空间。具体代码如下：

voidRemoveHead(LinkListhead)

{

ListNode*p;

p=head-＞next;

head-＞next=p-＞next;

free(p);

}

7.

如何找出单链表中的倒数第k个元素正确答案：为了找出单链表中的倒数第k个元素，最容易想到的方法是首先遍历一遍单链表，求出整个单链表的长度n，然后将倒数第k个，转换为正数第n-k个，接下去遍历一次就可以得到结果。但是该算法需要对链表进行两次遍历，第一次遍历用于求解单链表的长度，第二次遍历用于查找正数第n-k个元素。

于是想到了第二种方法，如果沿从头至尾的方向从链表中的某个元素开始，遍历k个元素后刚好达到链表尾，那么该元素就是要找的倒数第k个元素。根据这一性质，可以设计如下算法：从头结点开始，依次对链表的每一个结点元素进行这样的测试，遍历k个元素，查看是否到达链表尾，直到找到那个倒数第k个元素为止。此种方法将对同一批元素进行反复多次的遍历，对于链表中的大部分元素而言，都要遍历k个元素，如果链表长度为n，该算法时问复杂度为O(kn)级，效率太低。

存在另外一种更高效的方式，只需要一次遍历即可查找到倒数第k个元素。由于单链表只能从头到尾依次访问链表的各个结点，所以如果要找链表的倒数第k个元素，也只能从头到尾进行遍历查找。在查找过程中，设置两个指针，让其中一个指针比另一个指针先前移k-1步，然后两个指针同时往前移动。循环直到先行的指针值为NuLL时，另一个指针所指的位置就是所要找的位置。程序代码如下：

template＜classT＞

structListNode

{

Tdata;

ListNode*next;

};

template＜classT＞

ListN0de＜T＞*FindElem(ListNode＜T＞*head,intk)

{

ListNode＜T＞*ptr1,*ptr2;

ptr1=ptr2=head;

for(inti=0;i＜k;++i)∥前移k步

{

ptr1=ptr1-＞next;

}

while(ptr1!=NULL)∥循环检测

{

ptr1=ptr1-＞next;

ptr2=ptr2-＞next;

}

returnptr2;

}

8.

如何实现单链表反转正确答案：输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。链表结点定义如下：

structListNode

{

intm_nKey;

ListNode*m_pNext;

}

为了正确地反转一个链表，需要调整指针的指向，而与指针操作相关代码总是容易出错的。先举个例子看一下具体的反转过程。例如，1、m、n是3个相邻的结点，假设经过若干步操作，已经把结点1之前的指针调整完毕，这些结点的mpNext指针都指向前面一个结点。现在遍历到结点m，当然需要调整结点的m_pNext指针，让它指向结点1，但需要注意的是，一旦调整了指针的指向，链表就断开了，因为已经没有指针指向结点n，没有办法再遍历到结点n了，因此为了避免链表断开，需要在调整m的mpNext之前要把n保存下来。接下来试着找到反转后链表的头结点，不难分析出反转后链表的头结点是原始链表的尾结点，即mpNext为空指针的结点。

具体的实现过程如下：

ListNode*ReverseIteratively(ListNode*pHead)

{

ListNode*pReversedHead=NULL;

ListNode*pNode=pHead;

ListNode*pPrev=NULL;

while(pNode!=NULL)

{

ListNode*pNext=pNode-＞m_pNext;

if(pNext==NULL)

pReversedHead=pNode;

pNode-＞m_pNext=pPrev;

pPrev=pNode;

pNode=pNext;

}

returnpReversedHead;

}

如果本题简化为逆序输出单链表元素，那么递归将是最简单的方法。在递归函数之后输出当前元素，这样能确保输出第n个结点的元素语句永远在第n+1个递归函数之后执行，也就是说第n个元素永远在第n+1个元素之后输出，最终先输出最后一个元素，然后是倒数第2个、倒数第3个，直到输出第一个元素位置。具体实现过程如下：

voidPrintReverseLink(ListNode*head)

{

if(head-＞Next!=null)

{

PrintReverseLink(head-＞m_pNext);

printf("%d\n",head-＞m_Next-＞m_nKey);

}

}

本题不是要求逆序输出，而是需要把单链表逆序，所以在使用递归思想的时候，还需要处理递归后的逻辑问题。具体而言，是在反转当前结点之前先调用递归函数反转后续结点，不过该方法存在一个问题，就是反转后的最后一个结点会形成一个环，所以必须将函数返回的结点的mpNext域设置为NULL，同时考虑到链表反转时需要改变head指针，所以在进行参数传递时，需要传递引用。

具体的实现过程如下：

ListNode*Reverse(ListNode*p,ListNode*&head)

{

if(p==NULL‖p-＞m_pNext==NULL)

{

head=p;

returnp

}

else

{

ListNode*temp=Reverse(p-＞m_pNext,head);

temp-＞m_pNext=p;

returntemp;

}

}

需要注意的是，当单链表有环时，就会无法反转，因为如果单链表有环，则存在两个结点指向同一结点的情况。如果反转就变成一个结点指向两个了，而这对于单链表是不可能的。

9.

如何从尾到头输出单链表正确答案：structListNode

{

intm_nKey;

ListNode*m_pNext;

};

从头到尾输出单链表比较简单，于是很自然地想把链表中链接结点的指针反转过来，改变链表的方向，然后就可以从尾到头输出了，但该方法需要额外的操作，是否还有更好的方法呢?答案是肯定的。

接下来的想法是从头到尾遍历链表，每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始输出结点的值，此时输出的结点的顺序已经反转过来了。该方法虽然没有只需要遍历一遍链表，但是需要维护一个额外的栈空间，实现起来会比较麻烦。

是否还能有更高效的方法?于是我们想到了第三种方法，既然想到了栈来实现这个函数，而递归本质上就是一个栈结构，于是很自然地又想到了用递归来实现。要实现反过来输出链表，每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点自身，这样链表的输出结果就反过来了。

具体实现如下：

voidPrintListReversely(ListNode*pListHead)

{

if(pListHead!=NULL)

{

PrintListReversely(pListHead-＞m_pNext);

printf("%d",pListHead-＞m_nKey);

}

}

该题还有两个常见的变体：

1)从尾到头输出一个字符串。

2)定义一个函数求字符串的长度，要求该函数体内不能声明任何变量。

对于这两个变体的解答，都可以参考本题的实现方式，在此就不再赘述了。

10.

如何寻找单链表的中间结点正确答案：最容易想到的思路是首先求解单链表的长度length，然后遍历length/2的距离即可查找到单链表的中间结点，但是此种方法需要遍历两次链表，即第一次遍历求解单链表的长度，第二次遍历根据索引获取中间结点。

如果是双向链表，可以首尾并行，利用两个指针一个从头到尾，一个从尾到头，当两个指针相遇的时候就找到中间元素。以此思想为基础，如果是单链表也可以采用双指针的方式来实现中间结点的快速查找。

第一步，有两个指针同时从头开始遍历。第二步，一个快指针一次走两步，一个慢指针一次走一步。第三步，快指针先到链表尾部，而慢指针则恰好到达链表中部(快指针到链表尾部，当链表长度为奇数时，慢指针指向的即是链表中间指针；当链表长度为偶数时，慢指针指向的结点和慢指针指向结点的下一个结点都是链表的中间结点)。

具体实现如下：

node*SearchMid(node*head)

{

node*temp=head;

node*mid=head;

while(head!=NULL&&head-＞next!=NULL&&head-＞next-＞next!=NULL)

{

head=head-＞next-＞next;

temp=temp-＞next;

mid=temp;

}

returnmid;

}

11.

如何进行单链表排序正确答案：最容易想到的排序算法是冒泡排序法，所以首先用冒泡排序法进行单链表的排序。程序示例如下：

#include＜stdio.h＞

#include＜stdlib.h＞

typedefstructnode

intdata;

structnode*next;

}linklist;

linklist*head=NULL;

linklist*CreateList(int*arr,intlen)

{

intdata;

linklist*pCurrent,*rear;

head=(linklist*)malloc(sizeof(linklist));

rear=head;

intcount=0;

while(count＜len)

{

pCurrent=(linklist*)malloc(sizeof(linklist));

pCurrent-＞data=arr[count];

rear-＞next=pCurrent;

rear=pCurrent;

count++;

}

rear-＞next=NULL;

returnhead;

voidShowList(linklist*p)

{

while(p)

{

printf("%d",p-＞data);

p=p-＞next;

}

printf("\n");

}

voidBubbleSortList(linklist*p)∥链表冒泡顺序

{

linklist*_temp=p-＞next;

linklist*_node=p-＞next;

inttemp;

for(;_temp-＞next;_temp=_temp-＞next)

{

for(_node=p-＞next;_node-＞next;_node=_node-＞next)

{

if(node-＞data＞_node-＞next-＞data)

{

temp=_node-＞data;

node-＞data=_node-＞next-＞data;

_node-＞next-＞data=temp;

}

}

}

intmain()

{

intarray[]={3,4,5,1,2,-1,7};

CreateList(array,sizeof(array)/sizeof(array[0]));

BubbleSortList(head);

ShowList(head-＞next);

return0;

}

程序输出结果：

-1123457

在各种排序算法中，冒泡排序并非最高效的。对链表这一特定数据结构而言，最好使用归并排序算法。而堆排序、快速排序这些在数组排序时性能非常好的算法，用在只能“顺序访问”的链表中却不尽如人意，但是归并排序却可以，它不仅保持了O(nlogn)的时间复杂度，而且它的空间复杂度也从O(n)降到了O(1)，除此之外，归并排序是分治法的实现。具体实现过程如下：

#include＜iostream＞

#defineMAXSIZE1024

#defineLENGTH8

usingnamespacestd;

typedefstruct

{

intr[MAXSIZE+1];

intlength;

}SqList;

voidMerge(SqListSR,SqList&TR,inti,intm,intn)

{

intj,k;

for(j=m+1,k=i;i＜=m&&j＜=n;++k)

{

if(SR.r[i]＜=SR.r[j])

TR.r[k]=SR.r[i++];

else

TR.r[k]=SR.r[j++];

}

while(i＜=m)

TR.r[k++]=SR.r[i++];

while(j＜=n)

TR.r[k++]=SR.r[j++];

voidMSort(SqListSR,SqList&TR1,ints,intt)

{

intm;

SqListTR2;

if(s==t)

TR1.r[s]=SR.r[t];

else

{

m=(s+t)/2;

MSort(SR,TR2,s,m);

MSort(SR,TR2,m+1,t);

Merge(TR2,TR1,s,m,t);

}

}

voidMergeSort(SqList&L)

MSort(L,L,1,L.length);

intmain()

{

inti;

SqListL={{0,49,38,65,97,76,13,27},LENGTH};

MergeSort(L);

for(i=1;i＜=L.length;i++)

cout＜＜L.r[i]＜＜"";

cout＜＜endl;

return0;

}

程序输出结果：

013273849657697

12.

如何实现单链表交换任意两个元素(不包括表头)正确答案：对于单链表而言，假设交换的结点为A与B，那么需要交换A与B的next指针以及AB直接前驱的next指针。需要注意的特殊情况：当A与B相邻时，此时需要做特殊处理；如果A与B元素相同，就没有必要交换；如果A与B结点中有一个是表头，也不交换。

程序示例如下：

structnode

{

intdata;

node*next;

};

node*FindPre(node*head,node*p)

{

node*q=head;

while(q)

{

if(q-＞next==p)

returnq;

else

q=q-＞next;

}

returnNULL;

}

node*Swap(node*head,node*p,node*q)

{

if(head==NULL‖P==NULL‖q==NULL)

{

cout＜＜"invalidparameter:NULL"＜＜endl;

returnhead;

}

if(p-＞data==q-＞data)

returnhead;

if(p-＞next==q)

{

node*pre_p=FindPre(head,p);

pre_p-＞next=q;

p-＞next=q-＞next;

q-＞next=p;

}

elseif(q-＞next==p)

{

node*pre_q=FindPre(head,q);

pre_q-＞next=p;

q-＞next=p-＞next;

p-＞next=q;

}

elseif(p!=q)

{

node*pre_p=FindPre(head,p);

node*pre_q=FindPre(head,q);

node*after_p=p-＞next;

p-＞next=q-＞next;

q-＞next=after_p;

pre_p-＞next=q;

pre_q-＞next=p;

}

returnhead;

}

13.

如何检测一个较大的单链表是否有环正确答案：单链表有环是指单链表中某个结点的next指针域指向的是链表中在它之前的某一个结点，这样在链表的尾部形成一个环形结构。检测单链表是否有环，一般有以下几种方法。

方法一：定义一个指针数组，初始化为空指针，从链表的头指针开始往后遍历，每次遇到一个指针就跟指针数组中的指针相比较，若没有找到相同的指针，说明这个结点是第一次访问，还没有形成环，将这个指针添加到指针数组中去。若在指针数组中找到了同样的指针，说明这个结点已经被访问过了，于是就形成了环。

方法二：定义两个指针fast与slow，slow的初始值指向头结点，fast的初始值指向头结点的下一点，slow每次前进一步，fast每次前进两步，两个指针同时向前移动，快指针每移动一次都要跟慢指针比较，直到当快指针等于慢指针为止，就证明这个链表是带环的单向链表，否则证明这个链表是不带环的循环链表(fast先行到达尾部为NULL，则为无环链表)。

structlisttype

{

intdata;

structlisttype*next;

};

typedefstructlisttype*list;

intIsLoop(lists11)

{

listfast=s11-＞next;∥较slow快一步，步长为1

listslow=s11;

if(fast==NULL‖fast==slow)∥判断链表长为2时是否相交

return-1;

while(fast!=NULL)

{

fast=fast-＞next;

slow=slow-＞next;

if(fast==slow)

return1;

}

}

方法三：通过使用STL库中的map表进行映射。首先定义map＜node*,int＞m；将一个node*指针映射成数组的下标，并赋值为一个int类型的数值。然后从链表的头指针开始往后遍历，每次遇到一个指针P，就判断m[p]是否为0。如果为0，则将m[p]赋值为1，表示该结点是第一次访问；而如果m[p]的值为1，则说明这个结点已经被访问过一次了，于是就形成了环。

程序代码示例如下：

map＜node*,int＞m;

boolIsLoop(node*head)

{

if(!head)

returnfalse;

node*p=head;

while(p)

{

if(m[p]==0)∥默认值都是0

m[p]=1;

elseif(m[p]==1)

returntrue;

p=p-＞next;

}

}

如果单链表有环，按照方法二的思路，走得快的指针fast若与走得慢的指针slow相遇时，slow指针肯定没有遍历完链表，而fast指针已经在环内循环了n圈(1≤n)。假设slow指针走了s步，则fast指针走了2s步(fast步数还等于S加上在环上多转的n圈)，设环长为r，则满足如下关系表达式：

2s=s±nr

s=nr

设整个链表长为L，入口环与相遇点距离为x，起点到环入口点的距离为a。则满足如下关系表达式：

a+x=nr

a+x=(n-1)r+r=(n-1)r+L-a

a=(n-1)r+(L-a-x)

(L-a-x)为相遇点到环入口点的距离，从链表头到环入口点的距离=(n-1)*循环内环+相遇点到环入口点，于是从链表头与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

程序代码如下：

list*FindLoopPort(list*head)

{

list*slow=head,*fast=head;

while(fast&&fast-＞next)

{

slow=slow-＞next;

fast=fast-＞next-＞next;

if(slow==fast)break;

}

if(fast==NULL‖fast-＞next==NULL)

returnNULL;

slow=head;

while(slow!=fast)

{

slow=slow-＞next;

fast=fast-＞next;

}

returnslow;

}

14.

如何判断两个单链表(无环)是否交叉正确答案：单链表相交是指两个链表存在完全重合的部分(注意，不是交叉到一个点)。判断两个单链表是否交叉，一般有两种方法：

1)将这两个链表首尾相连，然后检测看这个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。

2)利用链表相交的性质，如果两个链表相交，那么两个链表从相交点到链表结束都是相同的结点，必然是Y字形，所以判断两个链表的最后一个结点是不是相同即可。即先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交，这时记下两个链表的长度length，再遍历一次，长链表结点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

程序代码实现如下：

boolIsIntersect(Node*list1,Node*list2,Node*&value)

{

value=NULL;

if(list1==NULL‖list2==NULL)

returnfalse;

Node*temp1=list1,*temp2=list2;

intsize1=0,size2=0;

while(temp1-＞next)

{

temp1=temp1-＞next;

++size1;

}

while(temp2-＞next)

{

temp2=temp2-＞next;

++size2;

}

if(temp1==temp2)

{

if(size1＞size2)

while(size1-size2＞0)

{

list1=list1-＞next;

--size1;

}

if(size2＞size1)

while(size2-size1＞0)

{

list2=list2-＞next;

--size2;

}

while(list1!=list2)

{

list1=list1-＞next;

list2=list2-＞next;

}

value=list1;

returntrue;

}

else

returnfalse;

}

15.

如何删除单链表中的重复结点正确答案：一个没有排序的链表，如list={a,1,x,b,e,f,f,e,a,g,h,b,m}，请去掉重复项，并保留原顺序，以上链表去掉重复项后为newlist={a,1,x,b,e,f,g,h,m}，请写出一个高效算法。

方法一：递归求解。

linkdelSame(linkhead)

{

linkpointer,temp=head;

if(head-＞next==NULL)

returnhead;

head-＞next=delSame(head-＞next);

pointer=head-＞next;

while(pointer!=NULL)

{

if(head-＞number==pointer-＞number)

{

temp-＞next=pointer-＞next;

free(pointer);

pointer=temp-＞next;

}

else

{

pointer=pointer-＞next;

temp=temp-＞next;

}

}

returnhead;

}

采用递归方法效率不够高效，于是想到了方法二的Hash法。

方法二：使用Hash法，具体过程如下。

1)建立一个hash_map，key为链表中已经遍历的结点内容，开始时为空。

2)从头开始遍历链表中的结点。

①如果结点内容已经在hash_map中存在，则删除此结点，继续向后遍历。

②如果结点内容不在hash_map中，则保留此结点，将结点内容添加到hash_map中，继续向后遍历。

16.

如何合并两个有序链表(非交叉)正确答案：合并两个有序链表(假设链表元素为升序排列)，一般可以采用递归和非递归两种方式实现。

首先看递归方式，设两个链表的头结点分别为head1、head2，如果head1为空，则直接返回head2；如果head2为空，则直接head1。如果headl链表的第一个数据小于head2链表的第一个数据，则把head1链表的第一个元素存储到新合并的链表中，递归遍历去除第一个元素的head1链表和整个head2链表。如果head1链表的第一个元素大于或等于head2链表的第一个元素，则把head2链表的第一个元素存储到新合并的链表中，递归遍历整个head1链表，去除第一个元素的head2链表。具体过程如下：

Node*MergeRecursive(Node*head1,Node*head2)

{

if(head1==NULL)

returnhead2;

if(head2==NULL)

returnhead1;

Node*head=NULL;

if(head1-＞data＜head2-＞data)

{

head=head1;

head-＞next=MergeRecursive(head1-＞next,head2);

}

else

{

head=head2;

head-＞next=MergeRecursive(head1,head2-＞next);

}

returnhead;

}

使用非递归的方式时，分别用指针head1、head2来遍历两个链表，如果当前head1指向的数据小于head2指向的数据，则将head1指向的结点归入合并后的链表中；否则将head2指向的结点归入合并后的链表中。如果有一个链表遍历结束，则把未结束的链表连接到合并后的链表尾部。具体过程如下：

Node*Merge(Node*head,Node*head1,Node*head2)

{

Node*trap=head;

while(NULL!=head1&&NULL!=head2)

{

if(head1-＞data＜head2-＞data)

{

tmp-＞next=head1;

tmp=head1;

head1=head1-＞next;

}

else

{

tmp-＞next=head2;

tmp=head2;

head2=head2-＞next;

}

}

if(NULL!=head1)

{

tmp-＞next=head1;

}

if(NULL!=head2)

{

tmp-＞next=head2;

}

returntmp;

17.

什么是循环链表正确答案：循环链表(CircularLinkedList)是一种首尾相接的链表，它与单链表的唯一区别在于对尾结点的处理，因为在单链表中尾结点的指针域NULL改为指向头结点就得到了单循环链表。

在单循环链表上的操作基本上与非循环链表相同，只是将原来判断指针是否为NULL变为是否是头指针而已，没有其他较大的变化。图1所示为带头结点的单循环链表。

图1带头结点的单循环链表

a)非空表

b)空表

对于单链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点开始遍历整个链表。因为有时需要对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针rear来标识，可以使得操作效率得以提高。例如，用尾指针rear表示的单循环链表查找开始结点a1和尾结点an就很方便，此时查找时间复杂度都为O(1)。

例如，对两个单循环链表H1、H2的连接操作，是将H2的第一个数据结点接到H1的尾结点，若用头指针标识，则需要找到第一个链表的尾结点，其时间复杂性为O(n)；而链表若用尾指针R1、R2来标识，则时间性能为O(1)。操作如下：

p=R1-＞next;

∥保存R1的头结点指针

R1-＞next=R2-＞next-＞next;

∥头尾连接

free(R2-＞next);

∥释放第二个表的头结点

R2-＞next=p;

∥组成循环链表

具体过程如图2所示。

图2单循环链表连接

仅设尾指针rear的单循环链表的实现如下：

#include＜stdio.h＞

#include＜stdlib.h＞

typedefstructnode

{

intdata;

structnode*next;

}linklist;

linklist*rear=NULL;

linklist*CreateSingleLoopList()

∥单循环链表的实现

{

int_data;

linklist*pCurrent,*head;

head=(linklist*)malloc(sizeof(1inklist));

scanf("%d",&_data);

rear-＞data=_data;

rear-＞next=head;

head-＞next=rear;

scanf("%d",&_data);

while(_data!=-1)

{

pCurrent=(linklist*)malloc(sizeof(linklist));

pCurrent-＞data=_data;

rear-＞next=pCurrent;

pCurrent-＞next=head;

rear=pCurrent;

scanf("%d",&_data);

}

returnrear;

voidGetRearHead(linklist*p)

∥取开始结点和尾结点

{

printf("%d,",p-＞data);∥终端结点an

printf("%d,",p-＞next-＞next-＞data);∥开始结点a1

}

intmain()

{

rear=(linklist*)malloc(sizeof(linklist));

CreateSingleLoopList();

GetRearHead(rear);

return0;

}

18.

如何实现双向链表的插入、删除操作正确答案：循环单链表的出现，虽然能够实现从任一结点出发沿着链能找到其前驱结点，但是时间复杂度为O(n)。如果希望从链表中快速确定某一个结点的前驱，另一个解决方法就是在单链表的每个结点里再增加一个指向其前驱的指针域pr。这样形成的链表中就有两条方向不同的链，被称为双向链表(DoubleLinkedList)。双向链表简称双链表，它是由头指针head唯一确定的。带头结点的双链表的某些运算变得方便。将头结点和尾结点链接起来，为双循环链表。

带头结点的双链表的结点结构如图1所示。

图1带头结点的双向链表

双链表的形式描述：

typedefstructdlistnode

{

DataTypedata;

structdlistnode*prior,*next;

}DListNode;

typedefDListNode*DLinkList;

DLinkListhead;

由于双链表的对称性，在双链表中能方便地完成各种插入、删除操作。

在双向链表第i个结点P之前插入一个新的结点，则指针的变化情况如图2所示。

图2双向链表插入操作

具体实现代码如下：

voidDInsertBefore()

{

∥在带头结点的双链表中，将值为x的新结点插入*p之前，设p不等于NULL

DListNode*s=malloc(sizeof(DListNode));

s-＞data=x;

s-＞prior=p-＞prior;

s-＞next=p;

p-＞prior-＞next=s;

p-＞prior=s;

}

双链表上删除结点*p自身的操作如图3所示。

图3双向链表的删除操作

具体实现代码如下：

voidDDeleteNode(DListNode*p)

{

∥在带头结点的双链表中，删除结点*p，设*p为非终端结点

p-＞prior-＞next=p-＞next;

p-＞next-＞prior=p-＞prior;

free(p);

}

需要注意的是，与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(1)。

19.

为什么在单循环链表中设置尾指针比设置头指针更好正确答案：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便。设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear→next→next和rear，查找时间都是O(1)。

若用头指针来表示该链表，则查找终端结点的时间为O(n)。

20.

如何删除结点的前驱结点正确答案：假设在长度大于1的单循环链表中，既无头结点，也无头指针，s为指向链表中某个结点的指针，如何删除结点*s的直接前驱结点?

已知指向这个结点的指针是*s，那么要删除这个结点的直接前趋结点，首先需要找到一个结点，它的指针域是指向*s的，然后再把这个结点删除。具体过程如下：

voidDeleteNode(ListNode*s)

{

ListNode*P,*q;

p=s;

while(p-＞next-＞next!=s)

{

q=p;

p=p-＞next;

}

q-＞next=s;

free(p);

}

21.

如何实现双向循环链表的删除与插入操作正确答案：双向循环链表是双向链表和循环链表的综合。循环链表与单链表相同，是一种链式的存储结构。所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或表头结点，从而构成一个环形的链。在双向链表中，结点除含有数据域外，更有两个链域，一个存储直接后继结点地址，一般称为右链域；一个存储直接前驱结点地址，一般称为左链域。

与单链表类似，双向链表通常也是用头指针标识，也可以带头结点和做成循环结构，图1所示为带头结点的双向循环链表示意图。

图1带头结点的双向循环链表

通过某结点的指针P即可以直接得到它的后继结点的指针p-＞next，也可以直接得到它的前驱结点的指针p-＞prior，所以在有些操作中需要找前驱时，则必须再使用循环。例如，结点的删除操作。

设P是指向双向循环链表中的某一结点，即P是该结点的指针，则p→prior→next表示的是*P结点之前驱结点的后继结点的指针，即与P相等，而p→next→prior表示的是*p结点之后继结点的前驱结点的指针，也与P相等。

双向链表中结点的插入：设P指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*P的前面，插入过程如图2所示。

图2双向链表插入操作

操作如下：

1)s→prjor=p→prior。

2)p→prior→next=s。

3)s→next=p。

4)p→prior=s。

指针操作的顺序不是唯一的，但也不是任意的，第一步操作必须要放到第四步操作之前完成，否则*P的前驱结点的指针就丢掉了。

双向链表中结点的删除：设P指向双向链表中某结点，删除*P。操作过程如图3所示。

图3双向链表删除操作

操作如下：

1)p→prior→next=p→next。

2)p→next→prior=p→prior。

3)free(p)。

22.

如何在不知道头指针的情况下将结点删除正确答案：在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?

下面讨论3种链表的情况：

1)单链表。如果p指向的结点为链表尾结点，则无法删除，否则，可以将p指向结点的数据与p的后继结点交换，然后删除p的后继结点。

2)双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。

3)单循环链表。根据已知结点位置，可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以可以通过查找得到p结点的直接前趋。因此，可以删去p所指的结点。其时间复杂度应为O(n)。

23.

如何统计一行字符中有多少个单词正确答案：单词的数目可以由空格出现的次数决定(连续的若干个空格作为出现一次空格；一行开头的空格不统计在内)。如果测出某一个字符为非空格，而它的前面的字符是空格，则表示“新的单词开始了”，此时使单词数count累加1。如果当前字符为非空格而其前面的字符也是非空格，则意味着仍然是原来那个单词的继续，count不应再累加1。前面一个字符是否空格可以从word的值看出来，若word等于0，则表示前一个字符是空格；如果word等于1，意味着前一个字符为非空格。

程序示例如下：

#include＜stdio.h＞

#defineBUFFERSIZE1024

intmain()

{

charstring[BUFFERSIZE];

inti,count=0,word=0;

charc;

gets(string);

for(i=0;(c=string[i])!='\0';i++)

{

if(c=='')

word=0;

elseif(word==0)

{

word=1;

count++;

}

}

printf("一共有单词%d个n",count);

return0;

}

程序输出结果：

iamhehao

一共有单词3个

上例中(c=string[i])!='\0'的作用是先将字符数组的某一元素(一个字符)赋给字符变量c，此时赋值表达式的值就是该字符，然后再判定它是否是结束符。

24.

如何将字符串逆序正确答案：给定一个字符串s，将s中的字符顺序颠倒过来，如s="abcd"，逆序后变成s="dcba"。可以采用多种方法对字符串进行逆序，以下将对其中的一些方法进行分析。

(1)普通逆序

直接分配一个与原字符串等长的字符数组，然后反向拷贝即可。程序示例如下：

#include＜stdio.h＞

char*Reverse(char*s)

{

char*q=s;

while(*q++)

;

q-=2;

char*p=newchar[sizeof(char)*(q-s+2)];

char*r=p;

∥逆序存储

while(q＞=s)

*p++=*q--;

*p='\0';

returnr;

}

intmain()

{

chara[]="abcd";

intlen=sizeof(a)/sizeof(a[0]);

printf("%s\n",Reverse(a));

return0;

}

程序输出结果

dcba

(2)原地逆序

原地逆序不允额外分配空间，就是将字符串两边的字符逐个交换。例如，给定字符串“abcd”，逆序的过程分别是交换字符a和d，交换字符b和c。实现原地逆序的方式有以下3种。

1)设置两个指针，分别指向字符串的头部和尾部，然后交换两个指针所指的字符，并向中间移动指针直到交叉。

程序示例如下：

#include＜stdio.h＞

char*Reverse(char*s)

{

char*p=s;

char*q=s;

while(*q)

++q;

q-;

while(q＞p)

{

chart=*P;

*p++=*q;

*q--=t;

}

returns;

}

intmain()

{

chara[]="abcd";

intlen=sizeof(a)/sizeof(a[0]);

printf("%s\n",Reverse(a));

return0;

}

程序输出结果：

dcba

2)递归，需要给定逆序的区间，调用方法Reverse(s,0,strlen(s))，对字符串s在区间left和right之间进行逆序，程序代码示例如下：

char*Reverse(char*s,intleft,intright)

{

if(left＞=right)

returns;

chart=s[left];

s[left]=s[right];

s[right]=t;

Reverse(s,left+1,right-1);

}

3)非递归，同样指定逆序区间，和方法1)没有本质区别，一个使用指针，一个使用下标。

char*Reverse(char*s,intLeft,intright)

{

while(left＜right)

{

chart=s[left];

s[left++]=s[right];

s[right--]=t;

}

returns;

}

(3)不允许临时变量的原地逆序

原地逆序虽然没有额外分配空间，但还是使用了临时变量，占用了额外的空间。如果不允许使用额外空间，主要有以下两种方法：第一种是异或操作，因为异或操作可以交换两个变量而无需借助第三个变量；第二种是使用字符串的结束符'\0'所在的位置作为交换空间，但这有个局限，只适合以'\0'结尾的字符串，对于不支持这种字符串格式的语言，就不能使用了。

1)异或操作。

#include＜stdio.h＞

char*Reverse(char*s)

{

char*r=s;

char*P=s;

while(*(p+1)!='\0')

++p;

while(p＞s)

{

*p=*p^*s;

*s=*p^*s;

*p=*p--^*s++;

}

returnr;

}

intmain()

{

chara[]="abcd";

intlen=sizeof(a)/sizeof(a[0]);

printf("%s\n",Reverse(a));

return0;

}

程序输出结果：

dcba

2)使用字符串结束符'\0'所在的位置作为交换空间。

程序示例如下：

#include＜stdio.h＞

char*Reverse(char*s)

{

char*r=s;

char*p=s;

while(*p!='\0')

++p;

char*q=p-1;

while(q＞s)

{

*p=*q;

*q--=*s;

*s++=*p;

}

*p='\0';

returnr;

}

intmain()

{

chara[]="abcd";

intlen=sizeof(a)/sizeof(a[0]);

printf("%s\n",Reverse(a));

return0;

}

程序输出结果：

dcba

(4)按单词逆序

给定一个字符串，按单词将该字符串逆序。例如。给定“Thisisasentence”，则输出是“sentenceaisThis”，为了简化问题，字符串中不包含标点符号。一共分两个步骤，第一步先按单词逆序得“sihTsiaecnetnes”，第二步整个句子逆序得到“sentenceaisThis”。

对于步骤一，关键是如何确定单词，这里以空格为单词的分界。当找到一个单词后，就可以使用上面讲过的方法将这个单词进行逆序，当所有的单词都逆序以后，将整个句子看做一个整体(即一个大的包含空格的单词)再逆序一次即可。

程序示例如下：

#include＜stdio.h＞

voidReverseWord(char*p,char*q)

{

while(p＜q)

{

chart=*p;

*p++=*q;

*q--=t;

}

}

char*Reverse(char*s)

{

char*p=s;

char*q=s;

while(*q!='\0')

{

if(*q==")

{

ReverseWord(p,q-1);

q++;

p=q;

}

else

q++;

ReverseWord(p,q-1);

ReverseWord(s,q-1);

returns;

}

intmain()

{

chara[]="Iamgladtoseeyou";

intlen=sizeof(a)/sizeof(a[0]);

printf("%s\n",Reverse(a));

return0;

}

程序输出结果：

youseetogladamI

引申：如何实现逆序打印?

与上题类似，还有一类题目要求逆序输出，而不要求真正地逆序存储。对于这个问题，可以首先求出字符串长度，然后反向遍历即可。程序示例如下：

#include＜stdio.h＞

#include＜string.h＞

voidReversePrint(constchar*s)

{

intlen=strlen(s);

for(inti=len-1;i＞=0;--i)

printf("%c",s[i]);

}

intmain()

{

chara[]="abcd";

ReversePrint(a);

printf("\n");

return0;

}

程序输出结果：

dcba

如果不想求字符串的长度，可以先遍历到末尾，然后再遍历回来，这要借助字符串的结束符'\0'。程序代码示例如下：

#include＜stdio.h＞

voidReversePrint(constchar*s)

{

constchar*p=s;

while(*p)

*p++;

--p;

while(p＞=s)

{

printf("%c",*p);

--p;

}

}

intmain()

{

chara[]="abcd";

ReversePrint(a);

printf("\n");

return0;

}

对于上述方法，也可以使用递归的方式完成。程序示例代码如下：

voidReversePrint(constchar*s)

{

if(*(s+1)!='\0')

ReversePrint(s+1);

printf("%c",*s);;

}

25.

如何找出一个字符串中第一个只出现一次的字符正确答案：如何找出一个字符串中第一个只出现一次的字符?例如，输入abac，则输出b。本题可以采用hash法来实现。首先申请一个长度为256的表，对每个字符hash计数即可。因为C/C++中的char有3种类型：char、signedchar和unsignedchar。char类型的符号是由编译器指定的，一般是有符号的，在对字符进行hash时，应该先将字符转为无符号类型；否则当下标为负值时，就会出现越界访问。

另外，可以用一个buffer数组记录当前找到的只出现一次的字符，避免对原字符串进行第二次遍历。

程序示例如下：

#inc