[Go] LeetCode 141. Linked List Cycle
2 min readJan 20, 2020
Description
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.Follow up:
Can you solve it using O(1) (i.e. constant) memory?
Solution
/*
Approach 1: Hash TableTime complexity : O(n)
Space complexity: O(n)
*/
type ListNode struct {
Val int
Next *ListNode
}type NodesSeen []*ListNodefunc hasCycle1(head *ListNode) bool {
nodesSeen := NodesSeen{}
for head != nil{
if nodesSeen.contain(head) {
return true
}
nodesSeen = append(nodesSeen,head)
head = head.Next
}
return false
}func(n NodesSeen) contain(head *ListNode) bool{
for _,val := range n{
if *val == *head{
return true
}
}
return false
}/*
Approach 2: Two Pointerstime complexity is O(N+K), which is O(n)
Space complexity : O(1).
*/
func hasCycle2(head *ListNode) bool {
if head == nil {
return false
}
slow := head
fast := head.Next
//Check whether the fast runner will eventually meet the slow runner or not
//if not, head has no cycle
for slow != nil && fast != nil && fast.Next != nil{
if *slow == *fast {
return true
}
slow = slow.Next
fast = fast.Next.Next
}
return false
}
