- 方法一:
- 通过快慢指针来检查单链表是否存在循环
- 判断是否是循环链表时,也设置两个指针,慢指针和快指针,让快指针比慢指针每次移动快两次。如果快指针追赶上慢指针,则为循环链表,否则不是循环链表,如果快指针或者慢指针指向NULL,则不是循环链表。
- (1)用两个指针p1和p2分别指向表头结点,即p1=p2=head
- (2)p1和p2分别采用1和2作为步长遍历该链表。(注意,p2应该检查当前结点的下一个结点是否为NULL)
- (3)如果p1或者p2遇到了NULL,则证明该链表没有环;若p1和p2在某时刻指向同一结点,则说明该链表有环。
- 方法二:
- (a)p从表头结点开始以1为步长遍历表,边遍历边将表反向
- (b)如果p遇到NULL,则说明表没有环
- (c)如果p最后等于head,则说明表有环,且记此时p所经过的表的结点数为l(l=2l1+c,l1和c的定义见方法一)
- (d)p再从表头结点开始以1为步长遍历表,边遍历边反向,当遍历到l/2时,停止,设两个指针p1,p2均指向当前结点,然后分别从两个方向同时以1为步长遍历表(其中一个需要边遍历,边反向链表),当他们第相遇时,当前结点即为环头结点。且此时链表还原成原来的链表。
给定一个单链表,只给出头指针h:
1、如何判断是否存在环?
2、如何知道环的长度?
3、如何找出环的连接点在哪里?
4、带环链表的长度是多少?
解法:
1、对于问题1,使用追赶的方法,设定两个指针slow、fast,从头指针开始,每次分别前进1步、2步。如存在环,则两者相遇;如不存在环,fast遇到NULL退出。
2、对于问题2,记录下问题1的碰撞点p,slow、fast从该点开始,再次碰撞所走过的操作数就是环的长度s。
3、问题3:有定理:碰撞点p到连接点的距离=头指针到连接点的距离,因此,分别从碰撞点、头指针开始走,相遇的那个点就是连接点。
4、问题3中已经求出连接点距离头指针的长度,加上问题2中求出的环的长度,二者之和就是带环单链表的长度。
判断是否存在环的程序:
1
2
3
4
5
6
7
8
9
10
11
12
13
|
bool IsExitsLoop(slist *head) { slist *slow = head, *fast = head;
while ( fast && fast->next )
{
slow = slow->next;
fast = fast->next->next;
if ( slow == fast ) break ;
}
return !(fast == NULL || fast->next == NULL);
} |
寻找环连接点(入口点)的程序:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
slist* FindLoopPort(slist *head) { slist *slow = head, *fast = head;
while ( fast && fast->next )
{
slow = slow->next;
fast = fast->next->next;
if ( slow == fast ) break ;
}
if (fast == NULL || fast->next == NULL)
return NULL;
slow = head;
while (slow != fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
} |
相关推荐
当它是空表,向后结点就只想了自己,这也是它与单链表的主要差异,判断node->next是否等于head。 代码实现分为四部分: 初始化 插入 删除 定位寻找 代码实现: void ListInit(Node *pNode){ int item; Node ...
这是一个单循环链表,具备基本的操作,在普通链表的基础上,实现了定长循环链表的循环输入,判断链表是否有环等较为特殊的操作。增删改查自然也有。
循环链表是一种特殊的链表,它的尾节点指向头节点,形成一个...1. 遍历循环链表时,需要额外判断循环结束的条件,否则会陷入死循环。 2. 插入和删除节点时,需要保证链表的循环结构不被破坏,需要仔细处理指针的修改。
从我画的循环链表图中,你应该可以看出来,它像一个环一样首尾相连,所以叫作“循环”链表。 操作 is_empty() 判断链表是否为空 length() 返回链表的长度 travel() 遍历 add(item) 在头部添加一个节点 append(item)...
1.循环链表的基本操作: 插入、删除、新建、销毁、查找、遍历、逆置、链表拼接、快慢指针查找中间结点; 2.几个经典的链表问题: 约瑟夫环、拉丁方阵、魔术师发牌问题、判断链表是否含有环
看到题目后的主要思路:先判断链表是否为环,若为环再进行环入口的判断,否则直接返回null 1.判断链表是否为环形链表相对容易,代码如下。主要思路是创建两个指针–快指针fast,步长为2;慢指针slow,步长为1。若...
给定一个链表,判断它是否有环。 为了表示给定链表中的循环,我们使用一个整数 pos 来表示链表中 tail 连接的位置(0 索引)。 如果 pos 为 -1,则链表中没有环。 给定一个整数数组 nums,找出其总和最大的连续子...
参数:链表(linklist L) 成功清空链表返回1 } 4、 检查单链表是否为空 int LinkedListEmpty(LinkedList L) { //函数功能:判断链表是否为空 参数:链表(linklist L) 链表为空时返回0,不为空返回1 } 5、 遍历单链表 ...
1.判断链表是否存在环型链表问题:判断一个链表是否存在环,例如下面这个链表就存在一个环: 例如N1->N2->N3->N4->N5->N2就是一个有环的链表,环的开始结点是N5这里有一个比较简单的解法。设置两个指针p1,p2。每次...
判断链表中是否有环 206: 反转单链表 876: 求链表中间结点 题目分类 栈 20: 有效的括号 155: 最小栈 232: 用栈实现队列(todo) 844: 比较含退格的字符串 224: 基本计算器 682: 棒球比赛 496: 下一个更大的元素 503: ...
判断链表中是否有环 快慢指针法。空间复杂度 O(1);时间复杂度 O(n) 判断链表中是否有环。如果有环求入口节点 Floyd法。先用快慢指针确定是否有环。如果有环找出相遇点。分别从相遇点和头节点出发,再次相遇时即是
二叉树的层次遍历及宽度,哈夫曼树,将L中的整数序列循环左移p个位置,将表L中所有值为x 的元素删除,判断链表中是否存在环,删除单链表L(L中元素值各不相同)的最大值所对应的结点,并返回该值,树的孩子兄弟表示...
测试一个链表是否是循环链表java实现 找出单链表的中间节点 求解约瑟环问题 单链表反转问题 最大子序列和问题 计算最大公因数 判断两个数组中是否有相同的数字 字符串反转
前端面试常考的要点数据结构链表单向链表判断环以及环入口双向链表循环链表各种树b+树b-树b*树红黑树二叉树满二叉树平衡二叉树哈夫曼树完全二叉树二叉查找树队列哈希
判断链表是否有环 反转链表 两个有序链表合并 求链表中间节点 删除倒数第n个节点 两个单链表的公共节点 leetcode建议练习题号: 业界应用 如何实现LRU缓存淘汰算法 stack & queue 栈、队列 知识点 栈 队列 双端队列 ...
约瑟夫环(循环单链表) 二、应用题 5. 表达式求解 6. 将两个有序线性表合并成一个有序线性表,并去掉重复元素。 7. 设有一个线性单链表,其结点值均为正整数,且按值从大到小链接。试写出一个算法,将该线性...
循环链表和单向链表基本一致,差别仅在于算法中循环的条件不是结点的指针是否为空,而是他们的指针是否等于头指针, 循环链表最后一个结点的 link 指针不为 0 (NULL),而是指向了表的前端。 为简化操作,在循环链表...
判断单向列表是否有环 206 翻转单向链表 237 删除链表元素 203 删除链表多个元素 206 翻转链表 141 环形链表 2021-05-15: 876 获取链表中间节点 20 判断括号是否成对 2021-05-16: 150后缀表达式 224基本计算器 856...
比如在判断一个链表是否存在环的leetcode题目中,初始代码是这样的 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution...
范例1-46 仅设表尾指针循环链表的合并 110 ∷相关函数:MergeList_CL函数 1.3.16 正序输出双向链表 113 范例1-47 正序输出双向链表 113 ∷相关函数:ListInsert函数 ListTraverse函数 1.3.17 逆向输出双向链表 ...