Copy Linked List với Random Pointer (Deep Copy) trong Python

Linked List: mỗi node có data và next pointer. Giả sử node có thêm random pointer trỏ đến node khác. Yêu cầu: deep copy list (copy data và random pointer).

Input: List 5 node với random pointer.

Output: 5->2->3->7->4->

Cách giải

1. Chèn node mới (copy data) sau mỗi node gốc.
2. Copy random pointer: new_node.random = old_node.random.next.
3. Tách list mới ra khỏi list gốc.

Ví dụ

class ListNode:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.random = None

def copyRandomList(head):
    if head is None:
        return head
    # B1: Chèn node copy sau mỗi node gốc
    curr = head
    while curr:
        new = ListNode(curr.data)
        new.next = curr.next
        curr.next = new
        curr = curr.next.next
    # B2: Copy random pointer
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next
    # B3: Tách list
    curr = head
    new_head = head.next
    while curr.next:
        temp = curr.next
        curr.next = curr.next.next
        curr = temp
    return new_head

def printList(head):
    curr = head
    while curr:
        rand = curr.random.data if curr.random else None
        print(curr.data, rand)
        curr = curr.next

# Tạo list test
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:")
printList(head)
copied = copyRandomList(head)
print("\nDeep Copy:")
printList(copied)

Kết quả

Original list:
1 3
2 1
3 5
4 5
5 2
Deep Copy:
1 3
2 1
3 5
4 5
5 2