CP #10 : Copy List With Random Pointer Problemi

 Problem surada.

Cozum

Verilen bir linked list'i kopyalamak trivial sayilabilir. Burada tek fark, her node, bir random alanina sahip ve hehangibir node'u isaret ediyor. Yani one-pass ile biz linked listi kopyalarken henuz bu node'u kopyalamamis olabiliriz. Bu gibi bir durumda bu nodu olsuturmaya calismak daha fazla karmasaya sebep olacaktir. 

Bunun yerine oncelikle tum linked listi kopyalayalim. Ve de her orjinal node'a karsilik, klon node'u tutan bir mapping yapisi olusturalim. (Bir python dictionary). Kopyalama islemi bittikten sonra, linked listi tekrar one pass ile traverse edip, random alanini guncelleyelim. Bu kadar basit ama implementasyonda can sikici corner case'ler olabilir. 

Implementasyon

def copyRandomList(self, head):

    # bos liste icin edge case kontrolu

    if not head:

        return None

    # orjinal_node -> klone node

    mapping = {}

    # ilk once listeyi kopyalayalim

    # ve mappingi olusturalim
    

    # burada heading degeri de tutuyoruz ki hersey bittikten sonra

    # yeni head degerini dondurecegiz.

    new_head = Node(head.val)

    new_tail = new_head

    cur = head.next

    

    # ilk node'u da mappinge ekelemeyi unutmayalim 

    mapping[head] = new_head

    

    wile cur:

        new_tail.next = Node(cur.val)

        mapping[cur] = new_tail.next

        cur = cur.next

        new_tail = new_tail.next    

    # simdi liste kopyalandi ve her orjinal node'a karsilik

    #  klone node'lari biliyoruz.

    # random alanini guncelleyebiliriz

    # None kontrolu yapmak zorundayiz cunku random alani bir node olabilecegi gibi

    # None de olabilir.

    new_head.random = None if not head.random else mapping[head]

    new_tail = new_head.next

    cur = head.next

    # listenin geri kalanini da guncelliyoruz

    while cur:

        new_tail.random = None if not cur.random else mapping[cur]

        cur = cur.next

        new_tail = new_tail.next

return new_head

Analiz

Iki kere one-pass seklinde listeyi traverse ettigimiz icin O(n), lineer bir kompleksitemiz var. Hafiza ise yine her elemani bir kere mapping hashmap'i icerisinde barindirdigimizdan lineer.