Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return
null.Follow up:
Can you solve it without using extra space?
题目意思：
第一个是判断链表里有没有环
第二个是如果有环，返回环的第一个节点，否则返回null。
因为两题解起来差不多，所以就做第二个就行了。
解题思路：
解法一：
注意，题目中有一个follow up。说接下来能不能在不使用额外空间的情况下解决。
好，我们就先来使用额外空间的。
首先想到的就是用hashmap。每遍历一个节点就存到hashmap里去，然后判断hashmap里是不是已经包含了下一个节点，如果包含，则说明是有环的，如果都遍历到最后一个节点了都不包含，就说明没有环存在。
好像C++的stl里头有一个hash_map容器，但是我更熟悉的是Java的HashMap，所以这一题果断选择用Java来做。
代码是酱紫的。
public class Solution {
public ListNode detectCycle(ListNode head) {
HashMap<ListNode,Integer> map = new HashMap<ListNode,Integer>();
while(head != null){
if(map.containsKey(head))
return head;
map.put(head,0);
head = head.next;
}
return null;
}
}
解法二：
好，看完了额外空间的，接下来就是不适用HashMap，在原来的链表上直接计算了。
使用两个指针……
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(true){
if(fast == null || fast.next == null){
return null;
}
slow = slow.next;
fast = fast.next.next;
if(slow == fast)
break;
}
int lenCal = 0;
do{
slow = slow.next;
lenCal++;
}
while(slow != fast);
slow = head;
fast = head;
for(int i = 0; i < lenCal; i++){
fast = fast.next;
}
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(true){
if(fast == null || fast.next == null){
return null;
}
slow = slow.next;
fast = fast.next.next;
if(slow == fast)
break;
}
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
以上三种方法都能AC。