My code:
/**
* 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 tortoise = head;
ListNode rabbit = head.next;
while (rabbit != null) {
if (rabbit == tortoise)
return true;
rabbit = rabbit.next;
if (rabbit == null)
return false;
rabbit = rabbit.next;
tortoise = tortoise.next;
}
return false;
}
}
My test result:
Paste_Image.png
这道题目不难，就是龟兔赛跑，快慢指针。
一个指针排在前面，每次走两步，一格指针摆在后面一格，每次走一步。
如果有环，进入环后，快的指针一定可以赶上慢的，或者说，碰到。
**
总结： 快慢指针， LinkedList
**
Anyway, Good luck, Richardo!
My code:
/**
* 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 || head.next == null)
return false;
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next;
fast = fast.next;
if (slow == fast)
return true;
}
return false;
}
}
快慢指针。
Anyway, Good luck, Richardo!
差不多的做法。
Anyway, Good luck, Richardo! -- 08/15/2016
