链表

学习数据结构与算法
2021-05-17 14:29 · 阅读时长13分钟
小课

链表也是多个元素的集合,但是这些元素在内存中并不是连续存储,而是通过额外存储的下一个节点指针来实现逻辑上的顺序连接。链表的节点一般由两个部分组成,一是数据,二是指向下一个节点的指针。链表有以下特点。

  1. 链表中的元素在内存上是不连续存储。
  2. 无需提前申请空间,链表长度自由扩展。

链表的优点有,删除和插入元素效率高,时间复杂度是O(1),但是访问特定节点效率低,需要逐个节点遍历。

例如,链表[1,2,3,4,5,6,7,8,9,10]的存储结构如下:

链表
123
0x18
0x12

存储的值

下一个节点的内存地址

内存地址

  • Head
    1
    0x02
    0x01
  • Head
    2
    0x07
    0x02
  • Head
    3
    0x04
    0x07
  • Head
    4
    0x00
    0x04
  • Head
    5
    0x05
    0x00
  • Head
    6
    0x03
    0x05
  • Head
    7
    0x08
    0x03
  • Head
    8
    0x06
    0x08
  • Head
    9
    0x09
    0x06
  • Head
    10
    null
    0x09

链表也是非常基础的数据结构,很多其它数据结构的底层数据存储方式都可以用链表来实现。比如说List、Stack、Queue等等。

常见的链表有以下这些。

  • 单链表,没有特殊说明,一般指的就是单链表。
  • 双向链表,相比单链表,在每个节点多加一个指向上一个节点的指针,这样就能够更灵活的操作链表。
  • 循环链表,将非循环链表的最后一个节点的next指针指向第一个节点,形成一个环路,就是循环链表,从循环链表的任何一个节点出发都能遍历整个链表。
加载中...

跟链表相关的题目,最经典的应该就是下面这道链表反转的题目。

反转链表

给你单链表的头节点head ,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

链表可以选用迭代或递归方式完成反转。

另外一道经典的题目,检测链表是否有环。

环形链表

给定一个链表,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

如果链表中存在环,则返回 true 。 否则,返回 false 。

进阶:你能用 O(1)(即,常量)内存解决此问题吗?

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
3→2→0→-4
     ↑_____↓

解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:true
1→2
↑_↓

解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:false

解释:链表中没有环。

提示:

  • 链表中节点的数目范围是 [0, 10^4]
  • -10^5 <= Node.val <= 10^5
  • pos 为 -1 或者链表中的一个 有效索引 。

判断是否有环,实际上也可以理解为链表节点是否会重复,所以最容易想到的是遍历链表,然后用哈希表来判断节点是否有重复,这种解法空间复杂度为O(N)。下面介绍一种O(1)的解法,还是用之前提到的双指针的技巧,准确来讲应该叫快慢指针,因为每一轮循环第一个指针(快指针)会走两步,而慢指针只走一步,这样如果链表有环的话,两个指针最终会在同一个节点相遇。

链表LinkedList单链表反转链表