题目描述
解题思路
环形链表我们很容易想到用一个 Set 集合，遍历链表把每一个节点加入到集合里，如果某个节点已经存在集合中，说明链表有环，但是题目要求用 O(1) 的空间复杂度，如果用 Set 的话就引入了额外的空间，空间复杂度是 O(n) 不满足题目要求，另外一种常见的思路是快慢指针，慢指针一次走一步，快指针一次走两步，如果链表有环的话，快慢指针一定会相遇，如果没环的话，快慢指针一定不会相遇，可以想象成两个人在学校操场跑步，跑的快的人的速度是跑的慢的人速度的两倍，因为操场是圆形的，所以跑的快的人和跑的慢的人一定会再次相遇，也就是跑的快的人超了跑的慢的人一圈的时候。
代码实现
哈希表
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if (head == null) return false; Set<ListNode> set = new HashSet<>(); while (head != null) { if (!set.add(head)) { return true; } head = head.next; } return false; } }
快慢指针
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if (head == null) return false; ListNode fast = head; ListNode slow = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true; } } return false; } }
提交记录
