Java leetcode-141 环形链表
程序员文章站
2022-06-19 12:47:57
如何判断一个链表是否有环呢?对于普通链表而言,链表末尾的指针域为null,如果链表有环,链表没有指针域为null结点。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。下面是代码实现过程,用我们熟悉的快慢指针比较简单public boolean hasCycle(ListNode head) { if(head...
LeetCode链接:https://leetcode-cn.com/problems/linked-list-cycle/
如何判断链表是否有环呢?
设想两个人朝同一个方向跑步,一个跑得快,一个跑得慢,跑得快的先进入环形跑道,跑上一段时间,跑的快的一定可以和跑的慢的相遇。
对于普通链表而言,链表末尾的指针域为null,如果链表有环,链表没有指针域为null结点。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
解决思路:
1.先进行链表判空
2.设置快慢指针fast和slow,均从head开始
3.只要fast指向结点不为空以及fast指向结点的指针域(next)不为空,slow向后走一步,fast向后走两步
4.在两个指针向后移动的过程中,如果出现slow和fast指向同一结点,则表明链表有环
5.循环正常结束时,表明slow和fast没有相遇 ,链表无环
实现代码
public boolean hasCycle(ListNode head) {
if(head == null){
return false;
}
//快慢指针
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
return true;
}
}
return false;
}
本文地址:https://blog.csdn.net/weixin_44874269/article/details/112588004