รายการที่เชื่อมโยงเป็นโครงสร้างข้อมูลเชิงเส้นซึ่งแต่ละโหนดมีสองบล็อก โดยที่หนึ่งบล็อกมีค่าหรือข้อมูลของโหนด และอีกบล็อกมีที่อยู่ของฟิลด์ถัดไป
สมมติว่าเรามีรายการที่เชื่อมโยง โดยที่แต่ละโหนดมีตัวชี้สุ่มซึ่งชี้ไปยังโหนดอื่นในรายการ ภารกิจคือการสร้างรายการให้เหมือนกับรายการเดิม การคัดลอกรายการจากรายการต้นฉบับซึ่งมีตัวชี้แบบสุ่มเรียกว่า 'Deep Copy' ของรายการที่เชื่อมโยง
ตัวอย่าง
อินพุต-1:
ผลลัพธ์:
5-> 2 -> 3 -> 7 ->4 ->
คำอธิบาย:
หากเราผนวกรายการใหม่ด้วยค่าของโหนดดั้งเดิมในรายการเชื่อมโยงที่กำหนดและแทนที่ตัวชี้สุ่มของรายการที่เชื่อมโยงดั้งเดิมด้วยโหนดถัดไปในรายการใหม่ มันจะกลายเป็น 5-> 2->3 -> 7-> 4->
แนวทางในการแก้ปัญหานี้
เรามีรายการที่เชื่อมโยงกับโหนดที่มีข้อมูลและตัวชี้แบบสุ่ม เพื่อให้ได้สำเนาของรายการที่เชื่อมโยงกับข้อมูลและตัวชี้สุ่ม ก่อนอื่นเราจะต่อท้ายโหนดใหม่ด้วยค่าเดียวกันหลังจากแต่ละโหนด สิ่งนี้จะสร้างโหนดที่ซ้ำกันหลังจากแต่ละโหนด
หลังจากการเริ่มต้น ให้ตรวจสอบเส้นทางของตัวชี้สุ่มในรายการ และวางตัวชี้สุ่มตามนั้นในโหนดที่สร้างขึ้นใหม่
ตอนนี้การแยกโหนดที่สร้างขึ้นใหม่หลังจากแต่ละโหนดในรายการดั้งเดิมจะสร้างสำเนาของรายการที่เชื่อมโยงอย่างลึกซึ้ง
- นำรายการที่เชื่อมโยงพร้อมช่องข้อมูลและตัวชี้ไปยังที่อยู่ของโหนดสุ่ม
- ฟังก์ชัน copyRandomList(listnode*head) รับโหนดส่วนหัวของรายการดั้งเดิมเป็นอินพุตและส่งคืนสำเนาแบบลึกของรายการ
- ถ้าหัวว่าง แสดงว่ารายการว่างและเราต้องคืนหัวด้วย
- ตอนนี้แทรกโหนดใหม่ที่มีค่าเดียวกันหลังจากแต่ละโหนดของรายการเดิม
- จากนั้นคัดลอกตัวชี้สุ่มจากรายการต้นฉบับและแทรกโหนดใหม่ นั่นคือ newnode->next =curr->randomPointer
- เมื่อสร้างโหนดใหม่ด้วยตัวชี้และข้อมูล เราจะแยกรายการและส่งคืนรายการเป็นผลลัพธ์
ตัวอย่าง
class listnode:
def __init__(self, data):
self.data = data
self.next = None
self.random = None
def copyRandomList(head):
if head is None:
return head
# Insert a new node with the same value after each node in the original list.
curr = head
while curr != None:
new = listnode(curr.data)
new.next = curr.next
curr.next = new
curr = curr.next.next
# Now place the randompointer with the newly created node.
curr = head
while curr != None:
curr.next.random = curr.random.next
curr = curr.next.next
# Now Let us separate the newly created list from the original list.
curr = head
temp = head.next
while curr.next != None:
dummyHead = curr.next
curr.next = curr.next.next
curr = dummyHead
return temp
def printList(head):
curr = head
while curr != None:
print(curr.data, " ", curr.random.data)
curr = curr.next
head = listnode(1)
head.next = listnode(2)
head.next.next = listnode(3)
head.next.next.next = listnode(4)
head.next.next.next.next = listnode(5)
head.random = head.next.next
head.next.random = head
head.next.next.random = head.next.next.next.next
head.next.next.next.random = head.next.next.next.next
head.next.next.next.next.random = head.next
print("Original list:\n")
printList(head)
copiedList = copyRandomList(head)
print("\n Deep Copy of the List:")
printList(copiedList) การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น
ผลลัพธ์
Original list: 1 3 2 1 3 5 4 5 5 2 Deep Copy of the List: 1 3 2 1 3 5 4 5 5 2
