[Go] LeetCode 141. Linked List Cycle

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 = 1Output: trueExplanation: There is a cycle in the linked list, where tail connects to the second node.`

Example 2:

`Input: head = [1,2], pos = 0Output: trueExplanation: There is a cycle in the linked list, where tail connects to the first node.`

Example 3:

`Input: head = [1], pos = -1Output: falseExplanation: There is no cycle in the linked list.`

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}`

Written by

TAKASHI NARIKAWA

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