题一、 给定单链表,检测是否有环。
使用两个指针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删除对应结点。
分享到:
相关推荐
C语言链表相关的面试题在软件开发领域的面试中是非常常见的,这是因为链表作为一种基本的数据结构,对于理解数据结构、算法以及内存管理等方面有着重要的作用。以下是一些关于C语言链表的面试题及其详细解释。 1. ...
数据结构,链表所有综合面试题型汇总,有大神漏缺的给我留言
这个工程里面记录了比较全面的链表的面试题,希望可以帮助需要的同学.
C语言链表类面试题.docx struct node { int data; struct node* next; }; 创建单链表的程序为: struct node* create(unsigned int n) { //创建长度为n的单链表 assert(n > 0); node* head; head = new ...
Linked lists of data structures often meet questions.
题一、给定单链表,检测是否有环。题二、 给定两个单链表(head1, head2),检测两个链表是否有交点,如果有返回第一个交点。等面试题。
链表是最基本的数据结构,凡是学计算机的必须的掌握的,在面试的时候经常被问到,关于链表的实现,百度一下就知道了。 在此总结一下与链表相关的练习题。题目很全,好好消化。
面试题总结:数组和链表的区别 数组和链表.pdf
微软面试题,输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。适合新手入门结构清晰易懂
算法大全-面试题-链表-栈-二叉树-数据结构
我们在找嵌入式方面的工作时,让我们头疼的恐怕就是面试题了,因为我们摸不到企业的命题规律,也不知道该怎样去准备,今天将各大企业的面试题进行汇总,分享给大家,希望可以帮到各位小伙伴。加油哦!
java基础面试题反转链表本资源系百度网盘分享地址
c数据结构面试题 比较经典 基本的链表、等操作,
面试题 02.07. 链表相交原题链接:面试题 02.07. 链表相交解法一:首尾相接法解题思路将这两个链表首尾相连,然后检测这个链表是否存在环,如果存在,则两
主要介绍了JAVA相关实现链表的面试题,代码实现非常详细,每一个方法讲解也很到位,特别适合参加Java面试的朋友阅读。
java基础面试题复杂链表的复制本资源系百度网盘分享地址
1、一个学生的信息是:姓名,学号,性别,年龄等信息,用一个链表,把这些学生信息连在一起, 给出一个age, 在些链表中删除学生年龄等于age的学生...里面有我自己从华为面试题里的汇总,有简答题和改错题,编程题等等.
面试题13 O(1)时间删除链表结点 面试题14 调整数组顺序使寄数位于偶数前面 3.4 代码的鲁棒性 面试题15 链表中倒数第k个结点 面试题16 反转链表 面试题17 合并两个排序的链表 面试题18 树的子结构 第4章 解决面试题...
java基础面试题链表中环的入口节点本资源系百度网盘分享链接