文档章节

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

小代码2016
 小代码2016
发布于 2015/02/21 15:58
字数 1321
阅读 28
收藏 1
点赞 0
评论 0

1.已知链表的头结点head,写一个函数把这个链表逆序

  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.         }  
  12.         head->next  = NULL;  
  13.         head = p;  
  14. }  

递归方法:

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

2.已知两个链表head1 和head2 各自有序,请把它们合并成一个链表依然有序。

  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随机指向链表中的任一个节点,可能是自己或者为空,写一个程序,要求复制这个链表的结构并分析其复杂性

这个题目的方法很巧妙,将两个链表连接起来形成一个链表,设置好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.         {  
  8.                 if(newhead == NULL){  
  9.                         newhead = new list_node;  
  10.                         newhead->value = cur->value;  
  11.                         newhead->next = cur->next;  
  12.                         cur->next = newhead;  
  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.         }  
  22.         cur = head;  
  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.         }  
  30.         cur = head;  
  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;  
  41.         newList.head = newhead;  
  42.         return newList;  
  43. }  

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

两个指针,一个步长为1,另一个步长为2.步长为2的走到底后步长为1的正好到中间。

  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,另一个步长为2,如果两个指针能相遇则有环。

  1. list_node * List::getJoinPointer()  
  2. {  
  3.   
  4.         if(head == NULL || head->next == NULL)return NULL;  
  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. }  

6. 给定单链表(head),如果有环的话请返回从头结点进入环的第一个节点。

设链表头到环入口节点距离为x,环入口节点到两个指针相遇节点距离为z,换长度为y,则有x+z+1=y,所以z=y-1-x,即一个指针从链表头部开始移动,一个指针两个指针相遇后一个节点开始移动,相遇的地方即为环入口

  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)指针,删除该结点。

将p后面那个节点的值复制到p,删除p后面的节点

  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前面插入一个节点

在p后面插入新节点,将p的值与新建的节点值互换。

 

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

一个指针指向链表头,另一个指针指向第k个指针,然后两个指针一起移动,第二个指针到了末端则第一个指针就是倒数第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;  
  9.         list_node * q=head;  
  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. 两个链表相交,找出交点

求出两个链表的长度a和b,一个指针指向较短链表的头head,另一个指针指向较长链表的第head+|a-b|,然后两个指针一起移动,相遇处即为交点。

  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;  
  8.         if(a<b){p=list.head;q = head;}  
  9.         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;  

本文转载自:http://blog.csdn.net/fatshaw/article/details/6452460

共有 人打赏支持
小代码2016
粉丝 35
博文 311
码字总数 153495
作品 0
安阳
程序员
九月十月百度,迅雷,华为,阿里巴巴最新校招笔试面试二十题(10.12)

九月十月百度,迅雷,华为,阿里巴巴,最新校招笔试面试二十题 题记 本博客自2010年10月11日开通以来,已经帮助了一大批人找到工作,特别是连续三年在每一年的9、10月份陪伴了至少三届毕业生...

mickelfeng ⋅ 2013/10/12 ⋅ 0

算法面试题总结

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

笨笨熊 ⋅ 2011/03/13 ⋅ 0

微软等公司数据结构+算法面试100题

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

chambai ⋅ 2012/08/05 ⋅ 0

(转)十月百度,阿里巴巴,迅雷搜狗最新面试七十题

(转)十月百度,阿里巴巴,迅雷搜狗最新面试十一题 来自:http://blog.csdn.net/vjulyv/article/details/6855788 引言 当即早已进入10月份,十一过后,招聘,笔试,面试,求职渐趋火热。而在这...

idea_biu ⋅ 2011/10/20 ⋅ 1

秒杀多线程第一篇 多线程笔试面试题汇总

系列前言 本系列是本人参加微软亚洲研究院,腾讯研究院,迅雷面试时整理的,另外也加入一些其它IT公司如百度,阿里巴巴的笔试面试题目,因此具有很强的针对性。系列中不但会详细讲解多线程同...

彭博 ⋅ 2012/04/12 ⋅ 0

迅雷2010校园招聘吉林大学第二次笔试题

迅雷2010校园招聘吉林大学第二次笔试题 答题时间: 2小时,请将答案写在答题纸上 一. 有n个文件的长度记载在一个无符号64 位整数数组中unsigned int64 filelength[n],把这n 个文件从逻辑上按...

长平狐 ⋅ 2013/01/06 ⋅ 0

秒杀多线程第一篇 多线程笔试面试题汇总

系列前言 本系列是本人参加微软亚洲研究院,腾讯研究院,迅雷面试时整理的,另外也加入一些其它IT公司如百度,阿里巴巴的笔试面试题目,因此具有很强的针对性。系列中不但会详细讲解多线程同...

晨曦之光 ⋅ 2012/05/21 ⋅ 0

数据结构与算法面试题80道

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

_子墨 ⋅ 2014/10/22 ⋅ 0

秒杀多线程第一篇 多线程笔试面试题汇总

系列前言 本系列是本人参加微软亚洲研究院,腾讯研究院,迅雷面试时整理的,另外也加入一些其它IT公司如百度,阿里巴巴的笔试面试题目,因此具有很强的针对性。系列中不但会详细讲解多线程同...

长平狐 ⋅ 2012/12/10 ⋅ 0

Appstore排名前十的程序员应用软件

程序员又名程序猿,苦逼劳累的代名词,曾经一个朋友这么开玩笑说,如果你是富二代,你当程序员就是脑残,如果你是穷二代,当程序员的话,死的时候一定是趴键盘。 程序员   哦,可怜的程序员...

程序员客栈 ⋅ 2016/05/14 ⋅ 1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

服务网关过滤器

过滤器作用 我们的微服务应用提供的接口就可以通过统一的API网关入口被客户端访问到了。但是,每个客户端用户请求微服务应用提供的接口时,它们的访问权限往往都需要有一定的限制,系统并不会...

明理萝 ⋅ 15分钟前 ⋅ 1

【2018.06.21学习笔记】【linux高级知识 14.1-14.3】

14.1 NFS介绍 NFS服务全称是NetWork File System:网络文件系统,最早有sun公司开发的,4.0版本由Netapp公司开发,是基于RPC远程过程调用(Remote Procedure Call)协议的服务。 14.2 NFS服务...

lgsxp ⋅ 24分钟前 ⋅ 0

Day18 vim编辑模式、命令模式与练习

编辑模式 命令模式 :nohl 不高亮显示 :x与:wq类似,如果在更改文件之后操作,两者效果一样;如果打开文件,没有任何操作; :wq会更改mtime,但是:x不会。 练习题 扩展 vim的特殊用法 ht...

杉下 ⋅ 27分钟前 ⋅ 0

Enum、EnumMap、EnumSet

1、Enum 不带参数 public enum Car { AUDI { @Override public int getPrice() { return 25000; } }, MERCEDES { ......

职业搬砖20年 ⋅ 28分钟前 ⋅ 0

Java中的锁使用与实现

1.Lock接口 锁是用来控制多个线程访问共享资源的方式,一般来说,一个锁能够防止多个线程同时访问共享资源。 在Lock出现之前,java程序是靠synchronized关键字实现锁功能的,而Java SE5之后,...

ZH-JSON ⋅ 29分钟前 ⋅ 0

线程组和 ThreadLocal

前言 在上面文章中,我们从源码的角度上解析了一下线程池,并且从其 execute 方法开始把线程池中的相关执行流程过了一遍。那么接下来,我们来看一个新的关于线程的知识点:线程组。 线程组 ...

猴亮屏 ⋅ 30分钟前 ⋅ 0

相对路径和绝对路径

基本概念   文件路径就是文件在电脑中的位置,表示文件路径的方式有两种,相对路径和绝对路径。在网页设计中通过路径可以表示链接,插入图像、Flash、CSS文件的位置。   物理路径:物理路...

临江仙卜算子 ⋅ 34分钟前 ⋅ 0

消息队列属性及常见消息队列介绍

什么是消息队列? 消息队列是在消息的传输过程中保存消息的容器,用于接收消息并以文件的方式存储,一个队列的消息可以同时被多个消息消费者消费。分布式消息服务DMS则是分布式的队列系统,消...

中间件小哥 ⋅ 37分钟前 ⋅ 0

java程序员使用web3j进行以太坊开发详解

如何使用web3j为Java应用或Android App增加以太坊区块链支持,教程内容即涉及以太坊中的核心概念,例如账户管理包括账户的创建、钱包创建、交易转账,交易与状态、智能合约开发与交互、过滤器...

笔阁 ⋅ 37分钟前 ⋅ 0

vim编辑模式、vim命令模式

vim编辑模式 使用vim filename 进入的界面是一般模式,在这个模式下虽然我们能够查看,复制,剪切,粘贴,但是不能编辑新的内容,如何能直接写入东西呢?这就需要进入编辑模式了,从一般模式...

李超小牛子 ⋅ 40分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部