Understand Linked List Cycle
Introduction
When I started studying algorithms with leetcode, I learned about a data structure called a linked list, so I made a note of it.
Difference between array and linked list
For arrays and linked lists, the following articles will be helpful. https://qiita.com/BumpeiShimada/items/522798a380dc26c50a50
The following articles will help you get an idea of the linked list. https://astrostory.hatenablog.com/entry/2020/02/24/070213
Try to solve the Leet Code problem
For details of the problem statement, please visit the letcode and check it. https://leetcode.com/problems/linked-list-cycle/
Excerpt from the problem statement 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.
The problem with this is that it returns True if the given linked list is looping, and False if it isn't.
I saw that this problem was solved in other articles, but I could not find an article on how to generate a linked list and return the output result, so I will also describe the processing of that part. did.
The key to this problem is to understand the address connections of the node objects created by ListNode.
The part that is not related to the processing result is commented, but in order to understand the connection of addresses, it is better to remove the comment and check it.
Solution 1 (using HashSet)
In this solution, node objects (addresses) are added to the empty set in order from the beginning. If you already have a node object that you want to add to the set, the linked list is considered circular.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head):
seen = set()
curr = head
# print(curr)
while curr: #Loop unless curr is None
if curr in seen:
# print(curr)
return True
seen.add(curr)
# print(seen)
curr = curr.next
# print(curr)
return False
# head = [3,2,0,-4]
# pos = 1 #pos is not a parameter, but indicates where the last element returns. (In this case, the last-4 returns to 2 of the first element)
#Creating a circular linked list
links = ListNode(3)
# print(vars(links))
links.next = ListNode(2)
# print(vars(links))
# print(vars(links.next))
links.next.next = ListNode(0)
# print(vars(links.next))
# print(vars(links.next.next))
links.next.next.next = ListNode(-4)
links.next.next.next.next = links.next #Back to 2(Circulate)
# print(vars(links.next.next.next))
# print(vars(links.next.next.next.next)) #Check circulation
# print(vars(links.next.next.next.next.next))
obj = Solution()
print(obj.hasCycle(links)) #True if circular
Solution 2 (using pointers with different speeds)
In this solution, a pointer called slow that transitions nodes one by one and a pointer that transitions nodes by skipping one are prepared. If the linked list is circular, slow and fast transitions at different rates will eventually point to the same address. From this, it is judged whether it is circulating.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head: #In leetcode, testcase may contain null, so describe it.
return False
slow = head #To the next pointer
fast = head.next #To the pointer two ahead
# print(slow, fast)
while slow != fast: #Loop unless slow and fast point to the same address (if circular, slow and fast with different speeds will eventually point to the same address)
if not fast or not fast.next: #linked if fast and fast are followed by null-Since list is over, it returns False
return False
slow = slow.next
fast = fast.next.next
print(slow, fast)
return True #Loop if slow and head reach the same node
# head = [3,2,0,-4]
# pos = 1 #pos is not a parameter, but indicates where the last element returns. (In this case, the last-4 returns to 2 of the first element)
#Circulation ex
links = ListNode(3)
# print(vars(links))
links.next = ListNode(2)
# print(vars(links))
# print(vars(links.next))
links.next.next = ListNode(0)
# print(vars(links.next))
# print(vars(links.next.next))
links.next.next.next = ListNode(-4)
links.next.next.next.next = links.next #Back to 2(Circulate)
# print(vars(links.next.next.next))
# print(vars(links.next.next.next.next)) #Check circulation
# print(vars(links.next.next.next.next.next))
#The first slow and fast addresses are links and links, respectively..Check if it matches next
# print(links)
# print(links.next)
obj = Solution()
print(obj.hasCycle(links)) #True if circular
#Confirmation of transition
# slow(Advance one by one)：3,2,0,-4
#fast (skip one): 2,-4,0 (2,0,-From the loop at 4)
#Therefore, slow and fast become the same node 0 address in two transitions, and the circulation is confirmed.
Postscript
You can also create a linked list by loop processing as shown below. The above links correspond to head.
#How to create a circular linked list 2
data = [3,2,0,-4]
# pos = 1 #pos is not a parameter, but indicates where the last element returns. (In this case, the last-4 returns to 2 of the first element)
#Create a linked list in a loop
tail = head = ListNode(data[0])
for i in data[1:]:
tail.next = ListNode(i) #The address is head for the first time.next, the second time head.next.next,3rd time head.next.next.next
tail = tail.next
head.next.next.next.next = head.next
# #Verification
# print(vars(head))
# print(vars(head.next))
# print(vars(head.next.next))
# print(vars(head.next.next.next))
# print(vars(head.next.next.next.next))
Summary
At first, it took some time to imagine the transition of the address, but it was fairly simple to understand. I would like to continue studying algorithms using leetcode.
reference
- https://astrostory.hatenablog.com/entry/2020/02/24/070213
- https://qiita.com/BumpeiShimada/items/522798a380dc26c50a50
- https://www.366service.com/jp/qa/aa4c5cab5dd27c1b42fa8a719933ed9f
Recommended Posts