🥈

Linked List Cycle II

Created

2022/01/20 10:20

문제 번호

142

카테고리

Hash Table

Linked List

Two Pointers

Linked List Cycle II - LeetCode

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.

https://leetcode.com/problems/linked-list-cycle-ii/

Code

제출 날짜	시간	메모리
2022/01/20	8 ms	5.2 MB

// 142. Linked List Cycle II
//
// https://leetcode.com/problems/linked-list-cycle-ii/

// Definition for singly-linked list.
// type ListNode struct {
//     Val int
//     Next *ListNode
// }

// detectCylce function detects whether the linked list has a cycle or not.
// Golang supports a pointer operation and taking address, so a hash map for address has been used.
// Maybe slow-fast algorithm which technique to reach the middle of the linked list can be used to check the list cyclic or not.
func detectCycle(head *ListNode) *ListNode {
	addressMap := make(map[*ListNode]bool)
	for head != nil {
		if !addressMap[head] {
			addressMap[head] = true
			head = head.Next
		} else {
			return head
		}
	}
	return nil
}
Go
복사