【百度面试题】从尾到头打印单鏈表数据结构(要求方式1:反向遍历方式2:Stack栈)
数组、链表数据结构等常用数据結构和集合浅解(java)
脑子转了一圈巴拉巴拉的写了一大堆,本来今天步行者打骑士的比赛在上半场已经花了步行者领先20多分,然而詹姆斯一个大大大号三双强行把比分拉回来还赢了比赛留下36分的乔治在风中发呆。
是计算机存储、组织数据的方式数据结构是指相互之間存在一种或多种特定关系的数据元素的集合。
顾名思义就是获取元素的工具。集合里面的类一般都实现Iterable接口并重写Iterator方法通过迭代器來操作元素
(List集合特有的迭代器 ,ListIterator 解决并发修改集合的问题,并且提供了更多操作元素的方法 )
集合是存储对象的且都是Object,由于对象具有多态等特点每次把元素取出肯定是需要向下转型,但是这个要转的类型并不确定于是这个强转的过程就有出错的可能。那么为了解决这个问题就需要用到泛型。使用泛型来规定这个集合只能存放某个类型的数据就不需要关心强转的问题了。
数组不够灵活集合提供了不同的类型来适应不同的场合。具体如下:
1 :数组能存放基本数据类型和对象而集合类中只能存放对象。
2 :数组容量固定集合類容量动态改变。
3 :数组无法判断其中实际存有多少元素 length 只告诉了数组的容量,而集合的 size() 可以确切知道元素的个数
4 :集合有多种实现方式和不同适用场合不像数组仅采用顺序表方式
5 :集合以类的形式存在,具有封装、继承、多态等类的特性通过自定义可以满足各种复雜操作,提高开发效率
Collections是一个 专门用来操作集合的工具类它提供了 搜索、排序、线程安全化等操作。
ArrayList由 数组实现在内存中分配连续空間,遍历元素和随机访问元素效率比较高
LinkedList由 链表数据结构实现插入、删除元素效率比较高
实现原理相同,功能相同都是长度可变的数組结构,很多时候可以互用 两者的主要区别如下
实现原理相同,功能相同底层都是哈希表结构,查询速度快在很多情况下可以互用, 两者的主要区别如下:
----摘自百度:(两幅图感觉列举得很形象)
----摘自百度:(两幅图感觉列举得很形象)
问题:现在有两个无环单链表数據结构若两个链表数据结构的长度分别为m和n,请设计一个时间复杂度为O(n + m)额外空间复杂度为O(1)的算法,判断这两个链表数据结构是否相交给定两个链表数据结构的头结点headA和headB,请返回一个bool值代表这两个链表数据结构是否相交。保证两个链表数据结构长度小于等于500
思路:詳见LB6,详见剑指offer. 理解什么是公共结点所谓公共结点是指这个结点是两个链表数据结构共有的,不是指具有相同值得两个结点由于这里巳知是无环单链表数据结构,因此两个链表数据结构一旦有公共结点,那么之后的链表数据结构一定是公共的即他们必然是尾部对其嘚Y字形。因此在尾部对齐的情况下,开头可以不是对齐的于是长链表数据结构经过几次移动直到与短链表数据结构对齐,之后开始一起移动遍历并使用==比较两个结点对象是否相同,如果相同直接返回即可。由于这里对于链表数据结构只需要进行遍历不需要进行返回因此直接对头结点pHead1,pHead2进行遍历即可不需要保留头结点。
普通方法:空间复杂度O(1)先将链表数据结构1中的所有结点放入到hash表中遍历链表數据结构2看每个结点在hash标中是否有记录,有记录说明就是交点
//输入两个链表数据结构,找到他们的第一个公共结点如果有公共结点,┅定是Y字形结构尾部对其。