Leetcode 138 Copy List with Random Pointer

Soru

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val

• random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

• Your code will only be given the head of the original linked list.

Örnek 1

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Örnek 2

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Örnek 3

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Çözüm

• Her düğümün iki işaretçi (pointer) içerdiği bir bağlı listede derin bir kopya (deep copy) yapmanızı ister. Bir işaretçi bir sonraki düğüme (next) işaret ederken, diğer işaretçi (random) liste içindeki herhangi bir düğüme veya hiçbir şeye işaret edebilir.
• Girdi: head, Node türünden bir bağlı listenin baş düğümü. Her Node iki işaretçi içerir: next ve random.
• Çıktı: Girilen bağlı listenin bir derin kopyası.
• Bu problemi çözmek için birkaç yaklaşım mevcuttur, ancak en yaygın olanı, liste üzerinde iki geçiş yaparak çözmektir:
• İlk Geçiş:Her düğüm için, yeni bir kopya düğümü oluşturun ve orijinal düğüm ile yeni düğüm arasına yerleştirin. Bu, original_node.next = copy_node ve copy_node.next = original_node.next şeklinde yapılır. Bu adım, yeni düğümlerin orijinal düğümlerin hemen ardına eklenmesini sağlar.
• İkinci Geçiş:random işaretçilerini güncelleyin. Orijinal düğümün random işaretçisi varsa, kopya düğümün random işaretçisi original_node.random.next olacaktır. Bu, yeni oluşturulan kopya düğümlere doğru işaret etmelerini sağlar.
• Üçüncü Geçiş:Kopya düğümleri orijinal düğümlerden ayırın ve kopya listesinin head’ini döndürün.
• Çalışma Mekanizması:
• Her orijinal düğüm için, yeni bir kopya düğüm oluşturulur ve bu, orijinal düğümün next’ine yerleştirilir.
• random işaretçiler, uygun şekilde kopyalanır.
• Liste ikiye ayrılarak orijinal ve kopya listeler ayrıştırılır.

Code

class Node:
    def __init__(self, val=0, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

class Solution:
    def copyRandomList(self, head):
        if not head:
            return None

        # İlk Geçiş: Yeni düğümleri oluştur ve orijinal düğümlerin arasına ekle
        current = head
        while current:
            new_node = Node(current.val, current.next, None)
            current.next = new_node
            current = new_node.next

        # İkinci Geçiş: Random işaretçileri kopyala
        current = head
        while current:
            if current.random:
                current.next.random = current.random.next
            current = current.next.next

        # Üçüncü Geçiş: Listeyi ayır ve kopya listeyi döndür
        current = head
        copy_head = head.next
        while current:
            temp = current.next
            current.next = temp.next
            if temp.next:
                temp.next = temp.next.next
            current = current.next

        return copy_head

Complexity

• Time complexity (Zaman Karmaşıklığı): O(n), burada n, liste içindeki düğüm sayısıdır. Her düğüm için birkaç kez geçiş yapılır.
• Space complexity (Alan Karmaşıklığı): O(1), ekstra alan yalnızca yeni düğümler için kullanılır; ek bir veri yapısı kullanılmaz.