คัดลอก Linked List ที่มี Random Pointer ใน Python

Linked List เป็นโครงสร้างข้อมูลเชิงเส้น (Linear Data Structure) ที่แต่ละ Node มี 2 ส่วน: ส่วนหนึ่งเก็บค่า/ข้อมูลของ Node อีกส่วนเก็บ Address ของ Next Field

สมมติว่าเรามี Linked List ที่แต่ละ Node มี Random Pointer ชี้ไปยัง Node อื่นใน List ภารกิจคือสร้าง List ใหม่ที่เหมือนกับ Original List การ Copy List จาก Original ที่มี Random Pointer เรียกว่า 'Deep Copy' ของ Linked List

ตัวอย่าง Input-1:

Output:

5-> 2 -> 3 -> 7 -> 4 ->

คำอธิบาย:

หากเรา Append Node ใหม่ด้วยค่าของ Original Nodes ใน Linked List ที่กำหนด และแทนที่ Random Pointer ของ Original List ด้วย Next Node ใน List ใหม่ จะได้ 5-> 2-> 3-> 7-> 4->

แนวทางแก้ปัญหา

เรามี Linked List ที่ Node มี Data Field และ Random Pointer เพื่อทำ Deep Copy พร้อม Data และ Random Pointer เราจะ Append Node ใหม่ด้วยค่าเดียวกันหลัง Node แต่ละตัว ซึ่งจะสร้าง Duplicate Node หลังแต่ละ Node

หลัง Initialization ตรวจสอบ Path ของ Random Pointer ใน List และวาง Random Pointer ตามนั้นใน Node ใหม่ที่สร้าง

ตอนนี้ แยก Node ใหม่ที่สร้างหลังแต่ละ Node ใน Original List จะได้ Deep Copy ของ Linked List

• รับ Linked List ที่มี Data Field และ Pointer ไป Address ของ Random Node

• Function copyRandomList(listnode* head) รับ Head Node ของ Original List คืนค่า Deep Copy

• ถ้า Head ว่าง List ว่าง คืนค่า Head

• Insert Node ใหม่ค่าเดียวกันหลัง Node แต่ละตัวของ Original List

• Copy Random Pointer จาก Original List ใส่ Node ใหม่: newnode->next = curr->randomPointer

• เมื่อสร้าง Node ใหม่พร้อม Pointer และ Data แล้ว แยก List และคืนค่า List เป็น Output

ตัวอย่าง

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 new node with same value after each node in original list
    curr = head
    while curr is not None:
        new = listnode(curr.data)
        new.next = curr.next
        curr.next = new
        curr = curr.next.next
    
    # Now place random pointer with newly created node
    curr = head
    while curr is not None:
        curr.next.random = curr.random.next
        curr = curr.next.next
    
    # Now separate the newly created list from original list
    curr = head
    temp = head.next
    while curr.next is not None:
        dummyHead = curr.next
        curr.next = curr.next.next
        curr = dummyHead
    return temp

def printList(head):
    curr = head
    while curr is not 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