I tried LeetCode every day 141. Linked List Cycle (Python, Go)
What is Leetcode
leetcode.com This is the practice of coding interviews for software developers. A total of more than 1,500 coding questions have been posted, and it seems that the same questions are often asked in actual interviews.
Introduction to golang + algorithm I will solve it with go and Python to strengthen the brain. (Python is weak but experienced)
32nd question (question 141)
- Linked List Cycle
the issue's details
Given
head, the head of a linked list, determine if the linked list has a cycle in it.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
nextpointer. Internally,posis used to denote the index of the node that tail'snextpointer is connected to. Note thatposis not passed as a parameter.Return
trueif there is a cycle in the linked list. Otherwise, returnfalse.Japanese translation
headIf given at the beginning of a linked list, determines if the linked list contains cycles.If there are nodes in the list that can be reached again by continuously following the
nextpointer, then there is a cycle in the linked list. Internally,posis used to indicate the index of the node to which the tailnextpointer is connected. ** Note that thisposis not passed as a parameter **.
true* Return * if there is a cycle in the linked list *. Otherwise, it returnsfalse.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Way of thinking
- Prepare fast that advances two nodes at a time and slow that advances only one node at a time.
- Loop processing until fast catches up with slow or runs out of values.
- True when catching up, False when nil
Answer code
def hasCycle(self, head):
slow = fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if slow == fast:
return True
return False
--I'll write it in Go too!
func hasCycle(head *ListNode) bool {
if head == nil || head.Next == nil {
return false
}
p1, p2 := head, head.Next
for p1 != p2 {
if p2 == nil || p2.Next == nil {
return false
}
p1 = p1.Next
p2 = p2.Next.Next
}
return true
}
Recommended Posts