【LeetCode练习题】Linked List Cycle II

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。

上一篇:15. Linked List Cycle && Linked List Cycle II


下一篇:Java for LeetCode 142 Linked List Cycle II