Leetcode[141, 142] Linked List Cycle
11 Nov 2015###Task1 Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space? ###Python ####O(n) extra space
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if not head:
return False
visit = set()
while head:
if head in visit:
return True
visit.add(head)
head = head.next
return False
####O(1) space
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if not head:
return False
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
###Java
/**
* 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.next;
while (fast != slow) {
if (fast == null || fast.next == null) {
return false;
}
fast = fast.next.next;
slow = slow.next;
}
return true;
}
}
###Points
- O(n)
###Task2 Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
###Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
visit = set()
while head:
if head in visit:
return head
visit.add(head)
head = head.next
return None
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
if slow != fast:
return None
fast = head
while fast != slow.next:
fast = fast.next
slow = slow.next
return fast
###Java
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode fast = head.next;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
while (head != slow.next) {
head = head.next;
slow = slow.next;
}
return head;
}
}
return null;
}
}
###Points
- head == slow.next, when the second time head pointer reach the enter point
- By the time slow reach enter point, (assume the length before is a), then fast has already go ‘a’ steps further inside the loop. So the distance between slow and fast until they meet is (assume the circumference is c) ‘c - a’ steps. At the time they two meet, slow will go ‘c - a’ further then the entry point. At this moment, we start another pointer from head, when the time head and slow meet(which is a) they will meet at the enter point.