题目：
141. Linked List Cycle(easy)
解题思路：
题目要求在O(1)的空间复杂度解决此问题。
这个题目是典型的双指针问题。
使用具有 不同速度 的快、慢两个指针遍历链表，空间复杂度可以被降低至O(1)。慢指针每次移动一步，而快指针每次移动两步。如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回false。否则两个指针总会相遇。
代码：
代码写法上有两种：
第一种:将慢指针看作不动得参考系，快指针的速度就从2视为1，当快指针走完一圈之后，就一定会于慢指针相遇。
1
2
3
4
5
6
7
8
9
10
11
| public boolean hasCycle(ListNode head) {
if(head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast) return true;
}
return false;
}
|
第二种：快指针先走一个，有环的话从后面追击慢指针
1
2
3
4
5
6
7
8
9
10
11
| public boolean hasCycle(ListNode head){
if(head == null || head.next == null) return false;
ListNode slow = head,fast = head.next;//快指针先走一个
while(slow != fast){
if(fast == null || fast.next == null)
return false;//走到最后也没找到
slow = slow.next;
fast = fast.next.next;
}
return true;
}
|
v1.5.2