链表相关面试题
题一、 给定单链表,检测是否有环。
使用两个指针p1,p2从链表头开始遍历,p1每次前进一步,p2每次前进两步。如果p2到达链表尾部,说明无环,否则p1、p2必然会在某个时刻相遇(p1==p2),从而检测到链表中有环。
题二、 给定两个单链表(head1, head2),检测两个链表是否有交点,如果有返回第一个交点。
如果head1==head2,那么显然相交,直接返回head1。
否则,分别从head1,head2开始遍历两个链表获得其长度len1与len2。假设len1>=len2,那么指针p1由head1开始向后 移动len1-len2步。指针p2=head2,下面p1、p2每次向后前进一步并比较p1p2是否相等,如果相等即返回该结点,否则说明两个链表没有 交点。
题三、 给定单链表(head),如果有环的话请返回从头结点进入环的第一个节点。
运用题一,我们可以检查链表中是否有环。
如果有环,那么p1p2重合点p必然在环中。从p点断开环,方法为:p1=p, p2=p->next, p->next=NULL。此时,原单链表可以看作两条单链表,一条从head开始,另一条从p2开始,于是运用题二的方法,我们找到它们的'第一个 交点即为所求。
题四、只给定单链表中某个结点p(并非最后一个结点,即p->next!=NULL)指针,删除该结点。
办法很简单,首先是放p中数据,然后将p->next的数据copy入p中,接下来删除p->next即可。
题五、只给定单链表中某个结点p(非空结点),在p前面插入一个结点。
办法与前者类似,首先分配一个结点q,将q插入在p后,接下来将p中的数据copy入q中,然后再将要插入的数据记录在p中。
题六、给定单链表头结点,删除链表中倒数第k个结点。
使用两个节点p1,p2,p1初始化指向头结点,p2一直指向p1后第k个节点,两个结点平行向后移动直到p2到达链表尾部(NULL),然后根据p1删除对应结点。
-
播音主持面试介绍集合15篇
播音主持面试介绍1各位老师好:我是xxx,来自景色神秘的湘西,宋祖英的家乡——古丈,家乡的水孕育了我温存和善的本性,家乡的山教会了我百折不挠的精神。在洪亮的山歌里诞生,在铿锵的鼓声中成长,作为一名土生土长的土家女孩,我喜爱?自己的家乡,但我更渴望看到外面的`世界,我...
-
面试邀请函【精品】
邀请函是商务礼仪与世俗礼仪的其中一部分。在快速变化和不断变革的今天,邀请函在活动中的使用越来越广泛,那么相关的邀请函到底怎么写呢?下面是小编为大家整理的面试邀请函,仅供参考,欢迎大家阅读。面试邀请函1您好!现诚邀您于4月29日下午来我司参加业务员岗位面试,如...
-
行政面试自我评价
在平凡的学习、工作、生活中,许多人都需要写自我评价,自我评价是个人对自己的思想、动机、行为和个性的评价。相信写自我评价是一个让许多人都头痛的问题,以下是小编为大家收集的行政面试自我评价,仅供参考,欢迎大家阅读。行政面试自我评价11.普通话标准,表达逻辑流...
-
面试简历自我评价集锦15篇
时间过得真快,总在不经意间流逝,又到了求职找工作的时候,此时是不是该好好写写简历呢?千万不能认为简历随便应付就可以喔,以下是小编为大家整理的面试简历自我评价,仅供参考,希望能够帮助到大家。面试简历自我评价1本人自学能力很强,在校自学了很多计算机知识,能熟练组...