LeetCode|LeetCode 环形链表

给定一个链表,判断链表中是否有环。进阶: 你能否不使用额外空间解决此题?

思路: 由于每一个父亲只有可能有一个孩子,故这里的环实际上是指链表中某一个节点的孩子同时也是它自己或者他的祖先。 这个问题需要注意下面几种情况:
  1. 空链表不成环
  2. 一个节点自环
  3. 一条链表完整成环
不能使用额外的空间,即空间复杂度是 O(1)。该问题是经典面试问题,其标准解法是用两个指针,一快一慢,如果在快的指针能够追上慢的指针,则有环,否则无环。
代码如下:
public boolean hasCycle(ListNode head) {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; }

【LeetCode|LeetCode 环形链表】思路参考自 [LeetCode-141] Linked List Cycle(判断链表是否有环)

    推荐阅读