试题5．给定单链表（head），如果有环的话请返回，从头结点进入环的第一个节点。
分析：设链表头到环入口节点距离为x，环入口节点到两个指针相遇节点距离为z，换长度为y，则有x+z+1=y，所以z=y-1-x，即一个指针从链表头部开始移动，一个指针两个指针相遇后一个节点开始移动，相遇的地方即为环入口。
答案：
01． list_node * List::findCycleEntry（）
02． {
03． if(checkCycle()==false)return NULL;
04． list_node * joinPointer = getJoinPoiter();
05． list_node * p = head;
06． list_node * q = joinPointer->next;
07． While(p!=q)
08． {
09． p=p->next;
10． q=q->next;
11． }
12． return p;
13． }
试题6．只给定单链表中某个结点p（并非最后一个结点，即p->next!=NULL）指针，删除该结点。
分析：将p后面那个节点的值复制到p，删除p后面的节点。
答案：
01． void List::deleteByPointer(list_node * node)
02． {
03． if(node)
04． {
05． if(node->next){
06． node->value = node->next->value;
07． node->next = node->next->next;
08． }
09． }
10． }
试题7．在单链表节点p前面插入一个节点。
分析：在p后面插入一个节点，然后将p的值与后面一个节点的值互换。
答案：类似试题6，忽略。
试题8．给定单链表头结点，删除链表中倒数第v个结点。
分析：一个指针指向链表头，另一个指针指向第k个指针，然后两个指针一起移动，第二个指针到了末端则第一个指针就是倒数第k个节点
答案：
01． list_node * List::lastKelement(int k){
02． Int t = k;
03． list_node * p = head;
04． while(p&&t){
05． p=p->next;
06． t- -;
07． }
08． if(p == NULL && t>0)return NULL;
09． list_node * q=head;
10． while(q && p){
11． p=p->next;
12． q=q->next;
13． }
14． return q;
15． }
试题9．判断两个链表是否相交。
分析：有两种情况。如果链表有环，则先在环里设定一个指针不动，另一个链表从头开始移动，如果另一个链表能够与环中的指针相遇则是相交。如果没有环，则判断两个链表的最后一个节点是否相同，相同则相交。
答案：
01． bool List::isIntersecting(const List & list)
02． {
03． bool flag = false;
04． if(this->checkCycle( ))
05． {
06． list_node * p = getJoinPointer( );
07． list_node * q = list.head;
08． while(q){
09． if(q == p){;
10． flag = true;
11． break;
12． }
13． q=q->next;
14． }
15． flag = true;
16． }
17． else
18． {
19． list_node * p = head;
20． list_node * q = list.head;
21． while(p->next)p=p->next;
22． while(q->next)q=q->next;
23． if(p == q)flag = true;
24． else flag =false;
25． }
26． Return flag;
27． }
试题10．两个链表相交，找出交点。（2009年华为校招笔试题。）
分析：求出两个链表的长度a和b，一个指针指向较短链表的头head；另一个指针指向较长链表的第head+|a-b|，然后两个指针一起移动，相遇处即为交点。
答案：
01． list_node * List::intersectNode(const List & list)
02． {
03． if(!isIntersecting(list))return NULL;
04． int a = cnt;
05． int b = list.cnt;
06． list_node * p;
07． list_node * q;
08． if(a<b){p=list.head; q = head;}
09． else{p = head; q=list.head;}
10． a = abs(cnt - list.cnt);
11． while(p && a)
12． {
13． p = p->next;
14． a- -;
15． }
16． while(p&&q)
17． {
18． if(q==p)break;
19． p=p->next;
20． q=q->next;
21． }
22． if(p && q && p == q)return p;
23． return NULL;
24． }
试题11．实现库函数strcpy(char * des, const char * src)。
答案：注意要点见本章2.1.2。
试题12．简答题：请说出树的深度优先、广度优先遍历算法，以及非递归实现的特点。
分析：该题考核的树的两种遍历方法在本章2.1.3中有所归纳。
答案：深度优先算法是一条分支一条分支进行遍历。广度优先是一层一层进行遍历。深度优先的非递归实现是利用栈，广度优先是利用队列。具体实现见本章2.1.3。
版权声明：51Testing软件测试网获作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可，不得对本文内容复制、转载或进行镜像，否则将追究法律责任。
