|
| 1 | +/** |
| 2 | + * |
| 3 | + */ |
| 4 | +packageeasy; |
| 5 | + |
| 6 | +importjava.util.HashMap; |
| 7 | +importjava.util.Map; |
| 8 | + |
| 9 | +importclasses.ListNode; |
| 10 | + |
| 11 | +/** |
| 12 | + * 141. Linked List Cycle QuestionEditorial Solution My Submissions |
| 13 | +Total Accepted: 120670 |
| 14 | +Total Submissions: 331612 |
| 15 | +Difficulty: Easy |
| 16 | +Given a linked list, determine if it has a cycle in it. |
| 17 | +
|
| 18 | +Follow up: |
| 19 | +Can you solve it without using extra space? |
| 20 | + * |
| 21 | + */ |
| 22 | +publicclassLinkedListCycle { |
| 23 | + |
| 24 | +/**Cheers! Easily made this one AC'ed, after a while since I first solved this problem, just sort out the logic, pretty straightforward.*/ |
| 25 | +publicbooleanhasCycle(ListNodehead) { |
| 26 | +ListNodeslow =head,fast =head; |
| 27 | +while(fast !=null &&fast.next !=null){ |
| 28 | +fast =fast.next.next; |
| 29 | +slow =slow.next; |
| 30 | +if(fast ==slow)returntrue; |
| 31 | +} |
| 32 | +returnfalse; |
| 33 | +} |
| 34 | + |
| 35 | +/**Then, I found there's an editorial solution for this question, it uses a Hashtable to store visited nodes, if current node |
| 36 | + * is null, that means we reach the end of the list, then there must not be a cycle in the list.*/ |
| 37 | +publicbooleanhasCycle_using_hashtable(ListNodehead) { |
| 38 | +Map<ListNode,Boolean>visited =newHashMap(); |
| 39 | +ListNodetemp =head; |
| 40 | +while(temp !=null){ |
| 41 | +if(visited.containsKey(temp))returntrue; |
| 42 | +visited.put(temp,true); |
| 43 | +temp =temp.next; |
| 44 | +} |
| 45 | +returnfalse; |
| 46 | +} |
| 47 | + |
| 48 | +} |