引入
我们学习了循环链表的基本操作,也学习了一个有趣的约瑟夫问题,我们之前说过有头指针也有尾指针,头指针指向头结点,尾指针指向尾结点。那么尾指针有哪些有趣的用法呢?
单循环链表的问题
我们知道,在单向循环链表中,我们有头指针
- O ( 1 ) 的时间去找到第一个结点,因为 next 就是头结点
- O ( n ) 的时间去找最后一个结点,因为第 n 个才是尾结点
如何在访问头结点和尾结点得时候,都是O( 1 )时间复杂度呢?
尾指针应运而生!
- 尾指针指向的是尾节点
- 而尾节点得下一个就是头结点
所以尾指针访问头结点和尾节点的时间都是 O ( 1 ) 。
撒花~~~
尾指针
我们看到这张图
- 尾指针的名称为 rear
- rear 指向得是终端结点的地址
- rear 的 next 元素为头结点
- 特点:特点就是可以灵活的操作头结点和尾结点
一个例题
创建两个单循环链表,将其合并成一个循环链表。
1 |
|
合并两个单循环链表有三个步骤
- 先把 A 的头结点的位置存下来
- A 的尾巴指向 B 的头结点
- B 得尾巴指向刚才存下在的 A 的头结点
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。