## 链表笔试面试题 -- 来自CSDN 转

小代码2016

1. void List::reverse()
2. {
3.         list_node * p = head;
4.         list_node * q = p->next;
5.         list_node * r = NULL;
6.         while(q){
7.                 r = q->next;
8.                 q->next = p;
9.                 p = q;
10.                 q = r;
11.         }
14. }

1. void List::reverse2(list_node * curnode)
2. {
4.         if(curnode->next==NULL)
5.         {
6.                 cur = curnode;
7.                 return;
8.         }
9.
10.         reverse2(curnode->next);
11.         curnode->next->next=curnode;
13.         {
15.                 cur = curnode;
16.                 cur->next = NULL;
17.         }
18. }

1. void List::merge(List & list)
2. {
3.         list_node * a = head;
4.         list_node * b = list.head;
5.         list_node * tempa= a;
6.         list_node * tempb = b;
7.         while(a&&b)
8.         {
9.                 if(a->value <= b->value)
10.                 {
11.                         while(a&&b&&a->value <= b->value)
12.                         {
13.                                 tempa = a;
14.                                 a = a->next;
15.                         }
16.                         tempa->next=b;
17.                 }
18.                 else
19.                 {
20.                         while(a&&b&&a->value > b->value)
21.                         {
22.                                 tempb = b;
23.                                 b = b->next;
24.                         }
25.                         tempb->next=a;
26.                 }
27.
28.         }
29. }

1. list_node* List::recursive_merge(list_node * a,list_node * b)
2. {
3.         if(a == NULL)return b;
4.         if(b == NULL)return a;
5.         if(a->value <= b->value){
6.                 a->next=recursive_merge(a->next,b);
7.                 return a;
8.         }
9.         if(a->value > b->value)
10.         {
11.                 b->next=recursive_merge(a,b->next);
12.                 return b;
13.         }
14. }

3.有一个链表L,其每个节点有2个指针，一个指针next指向链表的下个节点，另一个random随机指向链表中的任一个节点，可能是自己或者为空，写一个程序，要求复制这个链表的结构并分析其复杂性

1. List List::copyRndList()
2. {
3.         list_node * newhead = NULL;
4.         list_node * newcur = NULL;
5.         list_node * cur = head;
6.         while(cur)
7.         {
13.                 }
14.                 else{
15.                         newcur = new list_node;
16.                         newcur->value = cur->value;
17.                         newcur->next = cur->next;
18.                         cur->next = newcur;
19.                 }
20.                 cur=cur->next->next;
21.         }
23.         while(cur){
24.                 if(cur->rnd)
25.                         cur->next->rnd=cur->rnd->next;
26.                 else
27.                         cur->next->rnd = NULL;
28.                 cur = cur->next->next;
29.         }
31.         list_node * dst = cur->next;
32.         while(cur)
33.         {
34.                 list_node * temp = dst->next;
35.                 cur->next = temp;
36.                 if(temp)dst->next = temp->next;
37.                 cur = cur->next;
38.                 dst=dst->next;
39.         }
40.         List newList;
42.         return newList;
43. }

4. 找出单向链表中中间结点

1. list_node * List::middleElement()
2. {
3.         list_node * p = head;
4.         list_node * q = head->next;
5.         while(q){
6.                 p = p->next;
7.                 if(q)q=q->next;
8.                 if(q)q=q->next;
9.         }
10. }

5. 如何检查一个单向链表上是否有环

1. list_node * List::getJoinPointer()
2. {
3.
5.         list_node * one = head;
6.         list_node * two = head->next;
7.         while(one != two){
8.                 one = one->next;
9.                 if(two)two=two->next;
10.                 else break;
11.                 if(two)two=two->next;
12.                 else break;
13.         }
14.         if(one == NULL || two == NULL)return NULL;
15.         return one;
16. }

1. list_node * List::findCycleEntry()
2. {
3.         if(checkCycle()==false)return NULL;
4.         list_node * joinPointer = getJoinPointer();
5.         list_node * p = head;
6.         list_node * q = joinPointer->next;
7.         while(p!=q)
8.         {
9.                 p=p->next;
10.                 q=q->next;
11.         }
12.         return p;
13. }

7.只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。

1. void List::deleteByPointer(list_node * node)
2. {
3.         if(node)
4.         {
5.                 if(node->next){
6.                         node->value = node->next->value;
7.                         node->next = node->next->next;
8.                 }
9.         }
10. }

8.在p前面插入一个节点

9.给定单链表头结点，删除链表中倒数第k个结点

1. list_node * List::lastKelement(int k){
2.         int t = k;
3.         list_node * p = head;
4.         while(p&&t){
5.                 p=p->next;
6.                 t--;
7.         }
8.         if(p == NULL && t >0)return NULL;
10.         while(q && p){
11.                 p=p->next;
12.                 q=q->next;
13.         }
14.         return q;
15. }

10. 判断两个链表是否相交。

1. bool List::isIntersecting(const List & list)
2. {
3.         bool flag = false;
4.         if(this->checkCycle())
5.         {
6.                 list_node * p = getJoinPointer();
7.                 list_node * q = list.head;
8.                 while(q){
9.                         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. }

11. 两个链表相交，找出交点

1. list_node * List::intersectNode(const List & list)
2. {
3.         if(!isIntersecting(list))return NULL;
4.         int a = cnt;
5.         int b = list.cnt;
6.         list_node * p;
7.         list_node * q;
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;

### 小代码2016

mickelfeng
2013/10/12
0
0

2013/01/06
30
0

1.把二元查找树转变成排序的双向链表（树） 题目： 输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点，只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai
2012/08/05
0
0
Appstore排名前十的程序员应用软件

2016/05/14
4.1K
1
90 道名企笔试和算法题 (含答题讨论)

（点击上方公众号，可快速关注） 节选自「算法爱好者」微信公号的精选算法题和名企笔试题。 问：如何获取题目列表？ 答：① 长摁二维码关注「算法爱好者」，② 然后给它发送 名企笔试 或 算法...

Python开发者
01/21
0
0

CentOS配置Tomcat监听80端口,虚拟主机

Tomcat更改默认端口为80 更改的配置文件是: /usr/local/tomcat/conf/server.xml [root@test-a ~]# vim /usr/local/tomcat/conf/server.xml # 找到 Connector port="8080" protocol="HTTP/1......

5
0
《稻盛和夫经营学》读后感心得体会3180字范文

《稻盛和夫经营学》读后感心得体会3180字范文： 一代日本经营之圣稻盛和夫凭借刻苦勤奋的精神以及深植于佛教的商业道德准则，成为了“佛系”企业家的代表人物。在《稻盛和夫经营学》“领导人...

3
0
java框架学习日志-5（常见的依赖注入）

4
0

mbzhong

2
0
ActiveMQ消息传送机制以及ACK机制详解

AcitveMQ是作为一种消息存储和分发组件，涉及到client与broker端数据交互的方方面面，它不仅要担保消息的存储安全性，还要提供额外的手段来确保消息的分发是可靠的。 一. ActiveMQ消息传送机...

watermelon11

2
0