您现在的位置是:首页 > 后台技术 > 数据结构与算法数据结构与算法
环形链表(图文)
第十三双眼睛2023-11-29【数据结构与算法】人已围观
简介环形链表
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
思路:定义一个集合,来存放已经遍历过的节点,然后遍历链表,每遍历一个节点,看集合中是否存在,如果存在,就说明以前遍历过,表示存在环,如果不在集合中,就放入集合中,当遍历道的节点是空时,表示已经道末尾,返回false。代码如下:
思路二:龟兔赛跑法,定义两个辅助节点,一个快节点,一个慢节点,如果存在环,他们必定在某一时刻,会到达同一节点,此时返回true,如果没有环,则快的节点会先道达末尾,返回false。代码如下:
public static boolean method1(ListNode head) { ListNode current = head; Set<ListNode> set = new HashSet<>(); while (true) { if (current == null) { return false; } set.add(current); current = current.next; if (set.contains(current)) { return true; } } } |
思路二:龟兔赛跑法,定义两个辅助节点,一个快节点,一个慢节点,如果存在环,他们必定在某一时刻,会到达同一节点,此时返回true,如果没有环,则快的节点会先道达末尾,返回false。代码如下:
public static boolean method2(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; } |
Tags:
很赞哦! ()
上一篇:二叉树的后序遍历(图文)
下一篇:相交链表(图文)