[Go] Linked List - Linked List Cycle2(Detect Cycle)

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
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: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

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

 

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?

 

My code(floyd's tortoise and hare)

func detectCycle(head *ListNode) *ListNode {
	slow, fast := head, head
	hasCycle := false
	for slow != nil && fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			hasCycle = true
			break
		}
	}

	if hasCycle {
		slow = head
	} else {
		return nil
	}
	for slow != fast {
		slow = slow.Next
		fast = fast.Next
	}
	return slow
}

• I used floyd's tortoise and hare.
• The principle of this theory is that when the turtle pointer and the rabbit pointer meet, the turtle pointer is rotated first, the movement of the rabbit pointer is reduced from 2 to 1 , and if the movement proceeds, they meet at the beginning of the cycle.

My code(Map for storing address)

func detectCycle(head *ListNode) *ListNode {
	var s struct{}
	if head == nil {
		return nil
	}
	slow := head
	a := make(map[*ListNode]struct{})
	for slow.Next != nil {
		if _, ok := a[slow]; !ok {
			a[slow] = s
		} else {
			return slow
		}
		slow = slow.Next
	}
	return nil
}

sample 0 ms submission

func detectCycle(head *ListNode) *ListNode {
        if head == nil {
                return head
        }

        slow, fast := head, head
        
        for fast != nil && fast.Next != nil {
                slow, fast = slow.Next, fast.Next.Next
                if slow == fast {
                        // loop detected
                        start := head
                        for start != slow {
                                start, slow = start.Next, slow.Next
                        }
                        return slow
                }
        }
        
        return nil
}

• slow pointer can be used like also rabbit pointer because they are pointing same point.
• This code uses start variable to start from the beginning.

sample 1 ms submission

func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }
    
    slow, fast := head, head
    for slow != nil && fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            break
        }
    }
    
    if fast == nil || fast.Next == nil {
        return nil
    }
    
    slow = head
    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }
    
    return slow
}

sample 2 ms submission

func detectCycle(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    
    var slow, fast = head, head
    for {
        if fast == nil || fast.Next == nil || slow == nil {
            return nil
        }
        
        slow = slow.Next
        fast = fast.Next.Next
        
        if slow == fast {
            break
        }
    }
    
    var slow2 = head
    for slow2 != slow {
        slow, slow2 = slow.Next, slow2.Next
    }
    
    return slow
}

sample 3 ms submission

func detectCycle(head *ListNode) *ListNode {

	if head == nil || head.Next == nil {
		return nil
	}
    
	slow, fast := head, head
	var meetingPoint *ListNode
	for {
		if slow.Next == nil || fast.Next == nil || fast.Next.Next == nil {
			break
		}
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			meetingPoint = slow
			break
		}
	}

	if meetingPoint == nil {
		return nil
	}
	
	fromHead, fromMeetingPoint := head, meetingPoint
	for {
		if fromHead == fromMeetingPoint {
			return fromHead
			break
		}
		fromHead = fromHead.Next
		fromMeetingPoint = fromMeetingPoint.Next
	}

	return nil
}

sample 4 ms submission

func detectCycle(head *ListNode) *ListNode {
    if (head == nil || head.Next == nil) {
        return nil
    }
    
    slow := head
    intersection := meetPoint(head)
    if intersection == nil {
        return nil
    }
    
    for (slow != intersection) {
        slow = slow.Next
        intersection = intersection.Next
    }
    return slow
}

func meetPoint(head *ListNode) *ListNode {
    if (head == nil || head.Next == nil) {
        return nil
    }
    
    p1 := head
    p2 := head
    
    for (p1 != nil && p2 != nil) {
        if p1.Next != nil {
            p1 = p1.Next
        } else {
            p1 = nil
        }
        
        if p2.Next != nil {
            p2 = p2.Next.Next
        } else {
            p2 = nil
        }
        
        if p1 == p2 {
            return p1
        }
    }
    return nil
}

sample 5 ms submission

func detectCycle(head *ListNode) *ListNode {
        if head == nil || head.Next == nil {
                return nil
        }

        s, f := head, head
        for f != nil && f.Next != nil {
                s = s.Next
                f = f.Next.Next
                if s == f {
                        break
                }
        }

        if s != f {
                return nil
        }

        f = head
        for s != f {
                s = s.Next
                f = f.Next
        }
        return s
}

sample 6 ms submission

func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
		return nil
	}

	slow := head
	fast := head

	for {
		if slow.Next != nil {
			slow = slow.Next
		}

		if fast.Next != nil && fast.Next.Next != nil {
			fast = fast.Next.Next
		} else {
			return nil
		}

		if fast == slow {
			break
		}
	}

	slow = head
	for slow != fast {
		slow = slow.Next
		fast = fast.Next
	}

	return slow
}

sample 3600 KB submission

func detectCycle(head *ListNode) *ListNode {
    
    fast:=head
    slow:=head
    for fast!=nil && fast.Next!=nil{
        fast=fast.Next.Next
        slow=slow.Next
        if fast==slow {break}
    }
    if fast==nil || fast.Next==nil{
        return nil
    }
    
    slow=head
    for slow!=fast{
        slow=slow.Next
        fast=fast.Next    
    }
    return slow
}


func detectCycle_0(head *ListNode) *ListNode {
    fast:=head
    slow:=head
    
    for fast!=nil && fast.Next!=nil{
        fast=fast.Next.Next
        slow=slow.Next
        if fast==slow{
            break
        }
    }
    
    if fast==nil || fast.Next==nil{
        return nil
    }
    
    for head!=slow{
        head=head.Next
        slow=slow.Next
    }
    
    return slow
    
}

sample 3700 KB submission

func detectCycle(head *ListNode) *ListNode {
    
    fast,slow:=head,head
    
    for ;fast!=nil && fast.Next!=nil;{
        
        fast=fast.Next.Next
        slow=slow.Next
        

        if(fast==slow){
        slow=head
            for;;{
                if(fast==slow){
                    return slow
                }
                fast=fast.Next
            slow=slow.Next
            }
            
        }   
        
    }
    return nil
}

sample 3800 KB submission

func detectCycle(head *ListNode) *ListNode {
   if head == nil {
		return nil
	}

	fast := head
	slow := head

	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
		
		if fast == slow {
			// edge case: when head is the beginning of the cycle
			//if slow.Next == entry {
			//	return entry
			//}
			slow = head
			for fast != slow {
				fast = fast.Next
				slow = slow.Next
			}
			return slow
		}
	}

	return nil
}

sample 3900 KB submission

func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }
    fast := head
    slow := head
    for {
        if fast == nil || slow == nil || fast.Next == nil || slow.Next == nil {
            break
        }
        
        fast = fast.Next.Next
        slow = slow.Next
        
        if fast == slow {
            fast = head
            for fast != slow {
                fast = fast.Next
                slow = slow.Next
            }
            return fast
        }
    }
    
    return nil
}

sample 4000 KB submission

func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }
    hasCycle := false
    slow, fast := head, head.Next.Next
    for fast != nil && fast.Next != nil {
        if hasCycle = slow == fast; hasCycle {
            break
        }
        slow, fast = slow.Next, fast.Next.Next
    }
    if !hasCycle {
        return nil
    }
    seen := make(map[*ListNode]bool)
    for !seen[slow] {
        seen[slow] = true
        slow = slow.Next
    }
    for !seen[head] {
        head = head.Next
    }
    return head
}

sample 4900 KB submission

func detectCycle(head *ListNode) *ListNode {
    m := make(map[*ListNode]struct{})
    
    for head != nil {
        if _, ok := m[head]; ok {
            return head
        }
        
        m[head] = struct{}{}
        head = head.Next
    }
    
    return nil
}

• Simple than mine.