最先想到的是遍历链表, 并将结点的内存地址存在HashSet
中.如果当前结点的内存地址已经存在,则表示存在环,直接返回true
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
public class { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } Set<ListNode> set = new HashSet<>(); while (head != null) { if (set.contains(head)) { return true; }else { set.add(head); } head = head.next; } return false; } }
|
时间复杂度O(n)
空间复杂度O(n)
后来看了解析, 原来还有快慢指针的解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
|
public class { public boolean hasCycle(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; } }
|
近期评论