พิจารณาว่าเรามีรายการเชื่อมโยง และเราต้องตรวจสอบว่ามีวงจรหรือไม่ เพื่อแสดงวัฏจักรในรายการที่เชื่อมโยงที่กำหนด เราจะใช้ตัวชี้จำนวนเต็มหนึ่งตัวที่เรียกว่า pos ตำแหน่งนี้แสดงถึงตำแหน่งในรายการเชื่อมโยงที่มีการเชื่อมต่อหาง ดังนั้นหากตำแหน่งเป็น -1 แสดงว่าไม่มีวงจรอยู่ในรายการที่เชื่อมโยง ตัวอย่างเช่น รายการที่เชื่อมโยงเป็นเหมือน [5, 3, 2, 0, -4, 7] และ pos =1 ดังนั้นจึงมีวงจรและส่วนท้ายเชื่อมต่อกับโหนดที่สอง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เอาหนึ่งชุดเป็นชุดแฮช H
- ในขณะที่หัวไม่เป็นโมฆะ −
- ถ้า head อยู่ใน H ให้คืนค่า true
- ใส่หัว H
- หัว :=ข้างหัว
- คืนค่าเท็จ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
