一、链表:是一种基础数据结构,是一种线性表,不会按线性的顺序存储数据。
每一个结点存储一个数据和一个指向下一结点的地址(也叫后继指针next) 增、删的时间复杂度为O(1),查的时间复杂度为O(n)
1、常见链表
单链表:头结点记录链表基地址,尾结点的指针指向空地址null
循环链表:头结点记录链表基地址,尾结点的指针指向头结点
双向链表:每一个结点存储一个数据和一个指向下一结点的地址(也叫后继指针next),还有一个指向上一结点的地址(也叫前驱指针prev)
2、线性表(Linear List)。
线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组,链表、队列、栈等也是线性表结构。
二、leetcode题目
1、剑指 Offer 24. 反转链表
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例: 输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL
2、92. 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。
示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4输出: 1->4->3->2->5->NULL
3、141. 环形链表
给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回 true 。 否则,返回 false 。
4、剑指 Offer 25. 合并两个排序的链表
输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4
5、
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用?
- 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了?
- 找不到素材资源介绍文章里的示例图片?
- 模板不会安装或需要功能定制以及二次开发?
发表评论
还没有评论,快来抢沙发吧!