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。