[Go] LeetCode 141. Linked List Cycle

TAKASHI NARIKAWA
Jan 20 · 2 min read

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 Table
Time 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 Pointers
time 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
}

repo: https://github.com/fukubaka0825/LeetCodeInGo/blob/master/Algorithms/0141.linked_list_cycle/linked_list_cycle.go

TAKASHI NARIKAWA

Written by

Web developer in Tokyo. SRE/devops/Go/AWS/Terraform

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade