[Go] LeetCode 141. Linked List Cycle

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

--

--

--

Site Reliablity Engineer in Tokyo. SRE/devops/Go/AWS/Terraform/Kubernetes/Docker

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
TAKASHI NARIKAWA

TAKASHI NARIKAWA

Site Reliablity Engineer in Tokyo. SRE/devops/Go/AWS/Terraform/Kubernetes/Docker

More from Medium

LeetCode — Reverse Linked List II

[Leetcode] Find Median from Data Stream

Leetcode — Minimum Add to Make Parentheses Valid

Linked List | LeetCode Top Interview Questions