leetcode 141. Linked List Cycle 快慢指针

下一题 leetcode 142. Linked List Cycle II

题意

返回是否有环

解1

// 全部存下来 // Runtime: 3 ms, faster than 19.84% of Java online submissions for Linked List Cycle. //Memory Usage: 39.2 MB, less than 16.56% of Java online submissions for Linked List Cycle. public boolean hasCycle(ListNode head) { Set<ListNode> visited = new HashSet<>(); while (head != null) { if (visited.contains(head)) return true; visited.add(head); head = head.next; } return false; }

解2

龟兔赛跑，如果有环，必然能相遇。

// 快慢指针 // Runtime: 0 ms, faster than 100.00% of Java online submissions for Linked List Cycle. //Memory Usage: 38.8 MB, less than 16.56% of Java online submissions for Linked List Cycle. public boolean hasCycle(ListNode head) { if (head == null) return false; ListNode fast = head.next; while (fast != null && fast.next != null) { if (fast == head) return true; fast = fast.next.next; head = head.next; } return false; }