พิจารณาว่าเรามีลิงค์ลิสต์ และเราต้องตรวจสอบว่ามีวงจร (cycle) หรือไม่ เพื่อแทนวงจรในลิงค์ลิสต์ที่กำหนด เราจะใช้ตัวชี้จำนวนเต็มหนึ่งตัวชื่อ pos pos แทนตำแหน่งในลิงค์ลิสต์ที่ท้ายเชื่อมต่อ ถ้า pos เป็น -1 แสดงว่าไม่มีวงจรในลิงค์ลิสต์ เช่น ลิงค์ลิสต์เป็น [5, 3, 2, 0, -4, 7] และ pos = 1 มีวงจร และท้ายเชื่อมต่อกับโหนดที่สอง
วิธีการแก้ปัญหา
- ใช้เซตหนึ่งเป็นแฮชเซต H
- while head ไม่ใช่ null:
- ถ้า head อยู่ใน H ให้คืนค่า true
- เพิ่ม head เข้า H
- head := next ของ head
- คืนค่า False
ตัวอย่างโค้ด
class ListNode:
def __init__(self, data, next=None):
self.data = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def get_node(head, pos):
if pos != -1:
p = 0
ptr = head
while p < pos:
ptr = ptr.next
p += 1
return ptr
class Solution(object):
def hasCycle(self, head):
hashS = set()
while head:
if head in hashS:
return True
hashS.add(head)
head = head.next
return False
head = make_list([5,3,2,0,-4,7])
last_node = get_node(head, 5)
pos = 1
last_node.next = get_node(head, pos)
ob1 = Solution()
print(ob1.hasCycle(head))
อินพุต
List = [5,3,2,0,-4,7] Pos = 1
เอาต์พุต
True
