欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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/

如何判断链表是否有环呢?

设想两个人朝同一个方向跑步,一个跑得快,一个跑得慢,跑得快的先进入环形跑道,跑上一段时间,跑的快的一定可以和跑的慢的相遇。Java leetcode-141 环形链表

对于普通链表而言,链表末尾的指针域为null,如果链表有环,链表没有指针域为null结点。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
Java leetcode-141 环形链表

解决思路:

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