1.给定两个链表,判断是否有相交。
思路:首先明确一点,如果两个链表相交,那么从第一个交点开始到尾结点结束,所有的结点都是公共结点。
这也就是说,如果两个链表相交,那么这两个链表的尾结点肯定是公共结点,如果尾结点不是公共结点,那么这两个链表肯定不相交。
所以我们可以如下操作:依次遍历两个链表,最后判断尾结点是否相同,如果相同,则相交,如果不相同,则不相交。
复杂度:时间:O(m+n),m,n分别为两个链表的长度;空间:O(1)
2.给定两个链表,找到第一个公共结点。
思路:我们最容易想到的是从尾结点开始挨个向前比较,最后一个相同的就是第一个公共结点。
但是单链表只能从前往后进行遍历,如果想要从后往前的话则需要先从前向后遍历一次,同时用栈来记录每一个结点,最后出栈,然后挨个对比,这样的确可行,但是却要额外付出O(m+n)的空间。
仔细想想,我们可以先分别遍历两个单链表,记录长度m和n(无妨假设m>n),然后先让长度为m的链表向后走(m-n)步,接着两个链表同时向后遍历,第一个相同的结点就是要求的第一个公共结点。
复杂度:O(m+n),m,n分别为两个链表的长度;空间:O(1)
扩展:有的面试官为了考察学生的思维能力,会在上面基础上,要求每个链表只能遍历一次,可以对链表做任何修改。
这个也很简单,解法见:http://blog.csdn.net/alexander_xfl/article/details/12560249
3.给定一个链表,判断是否有环。
思路:这个是一个经典的问题了,思路也很简单,我们首先设置两个指针p1,p2同时指向链表的头部,然后p1每次向后走1步,p2每次向后走2步。
如果有环,那么有一步会出现p1=p2,如果p2已经到达了尾结点,则无环。
复杂度:时间:O(n),n是链表的长度;空间:O(1)
4.给定一个链表,找出环的入口位置。
思路:这个和3问题的基本思路一样,只是需要多做一步,那就是当p1=p2的时候,将p1重新指向链表的头结点,然后p1和p2都每次向后走一步,下一次p1=p2的结点就是环的入口。
复杂度:时间:O(n),n是链表的长度;空间:O(1)
这是在笔试面试中遇到的关于环的一些问题,今天总结了一下,供大家参考,算是了却了一桩心事。
如果大家还有关于链表的一些题目,欢迎留言或者发送邮件到alexander_xfl@163.com,我会及时更新。
分享到:
相关推荐
数据结构, 链表,笔试,很多次碰到,数据结构, 链表,笔试,很多次碰到。
uC/OS-II学习笔记—空闲链表和就绪链表
分别用C和C++实现了单向链表(创建链表,插入数据、获取指定位置的数据、删除指定位置的数据...),如果在使用中觉得api不够用可以进行扩展;其中包含测试。
C版本---DevC++打开 C++版本-----VS打开 主页面如下: 欢迎使用图书管理系统(管理员:admin 密码:password) 1.管理员登录 2.用户登录 3.用户注册 4.退出 管理员页面如下: 欢迎用管理员 1.显示所有图书 2....
C语言开发----链表HuffmanTree
数据结构(C语言版)---静态链表。这是博客配套代码。如果代码中有什么错误欢迎大家指出·············
哈希表--链表 哈希表--链表 哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表
数据结构实验线性表当中的链表结构实现,带有详细注释,小白也能看得懂
C/C++ 学生信息管理系统 链表 C/C++ 学生信息管理系统 链表
使用C++实现双向循环链表的增删改查排序等操作,可查看个人博客的【[数据结构和算法]C/C++双向循环链表实现(增删改查排序)】--链接https://blog.csdn.net/slimmm/article/details/84317806
本程序是用C语言实现的简单学生成绩管理,用到的主要知识点是链表,涉及到链表的建立,插入,节点的删除,排序等几乎所有的链表常用操作.模块强,可以根据需要自行裁减,原创作品!
数据结构课程练习---------------------------------------逆序链表的输入输出
自己写的一些关于链表的操作,包括单链表的排序和反转,双链表以及循环链表。
C语言程序设计-基于链表的学生成绩管理系统.doc
双链表-循环链表-静态链表.pdf
严蔚敏-数据结构--链表实现c++实现 还不错哦!``
C/C++ 学生信息管理系统 双链表C/C++ 学生信息管理系统 双链表
(完整word版)c++-学生信息管理系统-(链表+文件)-实验报告.doc
跨平台可复用C/C++库-XRDK的库和头文件,win32/vc8/x86。错误码定义,C、系统和网络错误获取,内存及字符串操作,常用数据结构(链表、环形数组、环形缓冲、动态缓冲)