线性表14 – 数据结构和算法19
线性表14
让编程改变世界
Change the world by program
循环链表的特点
回顾一下，在单链表中，我们有了头结点时，我们可以用O(1)的时间访问第一个结点，但对于要访问最后一个结点，我们必须要挨个向下索引，所以需要O(n)的时间。
大家猜的没错，如果用上今天我们学习到的循环链表的特点，用O(1)的时间就可以由链表指针访问到最后一个结点。
不过我们需要改造一下现有的循环链表，我们不用头指针，而是用指向终端结点的尾指针来表示循环链表，此时查找开始结点和终端结点都很方便了，如图：
循环链表的特点
那么按照这个逻辑的话，判断是否为空链表的条件应该如何呢？
就是判断rear是否等于rear->next，大家猜对了吗？
循环链表的特点是无须增加存储量，仅对链接方式稍作改变，即可使得表处理更加方便灵活。
一道例题
题目：
实现将两个线性表（a1，a2，…，an）和（b1，b2，…，bm）连接成一个线性表（a1，…，an，b1，…bm）的运算。
分析：
若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一个链表，找到结点an，然后将结点b1链到an的后面，其执行时间是O(n)。
若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。
循环链表的特点
稍作思考看代码实现：cennect.c
判断单链表中是否有环
有环的定义是，链表的尾节点指向了链表中的某个节点。
带环单链表
那么要判断单链表中是否有环，主要有以下两种方法：
方法一：使用p、q两个指针，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样。如图，当p从6走到3时，用了6步，此时若q从head出发，则只需两步就到3，因而步数不等，出现矛盾，存在环。
方法二：使用p、q两个指针，p每次向前走一步，q每次向前走两步，若在某个时候p == q，则存在环。
详细实现代码：loop.c
备用视频下载
技术, IT技术, 数据结构和算法, 链表
风险提示及免责条款
市场有风险，投资需谨慎。本文不构成个人投资建议，也未考虑到个别用户特殊的投资目标、财务状况或需要。用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资，责任自负。
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
