Week-4 CodeBuddy

w4p1.py

def mergeArray(a,b):
    m=len(b)
    n = len(a)-m
    for i in range(n//2):
        a[i], a[n-1-i] = a[n-1-i], a[i]
    k=len(a)-1
    i=n-1
    j=0
    while(i>=0 and j<m):
        if(a[i]<b[j]):
            a[k]=a[i]
            i-=1
        else:
            a[k]=b[j]
            j+=1
        k-=1
    while(j<m):
        a[k]=b[j]
        k-=1
        j+=1
    print(a)

a=[5,6,7,12,100,400,500,None, None, None, None]
b=[4,8,9,200]
mergeArray(a,b)

w4p2a.py

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

def cloneLinkedList(head):

    newHead=Node()
    temp=head.next
    prev=newHead
    randomHash={}

    while(temp!=None):
        tempNode=Node()
        prev.next=tempNode
        tempNode.val=temp.val
        randomHash[temp]=tempNode
        prev=tempNode
        temp=temp.next
    prev.next=None

    temp1=head.next
    temp2=newHead.next
    while(temp1!=None):
        temp2.random=randomHash[temp1.random]
        temp1=temp1.next
        temp2=temp2.next

    return newHead

head=Node()

node1=Node()
node1.val=1
head.next=node1

node2=Node()
node2.val=2
node1.next=node2

node3=Node()
node3.val=3
node2.next=node3

node4=Node()
node4.val=4
node3.next=node4

node1.random=node4
node2.random=node1
node3.random=node2
node4.random=node3

print("Original List with node values:",node1.val,node2.val,node3.val,node4.val)
print("Original List with random node values:",node1.random.val,node2.random.val,node3.random.val,node4.random.val)
newHead=cloneLinkedList(head)
print("Cloned List with values of the nodes:",newHead.next.val,newHead.next.next.val,newHead.next.next.next.val,newHead.next.next.next.next.val)
print("Cloned List with values of the random nodes:",newHead.next.random.val,newHead.next.next.random.val,newHead.next.next.next.random.val,newHead.next.next.next.next.random.val)

w4p2b.py

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

def cloneLinkedList(head):

    newHead=Node()
    temp=head.next

    while(temp!=None):
        tempNode=Node()
        if(newHead.next==None): newHead.next=tempNode
        tempNode.val=temp.val
        tempNode.next=temp.next
        temp.next=tempNode
        temp=temp.next.next

    temp=head.next
    while(temp!=None):
        temp.next.random=temp.random.next
        temp=temp.next.next

    temp=head.next
    while(temp!=None):
        cl_node=temp.next
        temp.next=cl_node.next
        if(cl_node.next!=None): cl_node.next=cl_node.next.next
        temp=temp.next
    return newHead

head=Node()

node1=Node()
node1.val=1
head.next=node1

node2=Node()
node2.val=2
node1.next=node2

node3=Node()
node3.val=3
node2.next=node3

node4=Node()
node4.val=4
node3.next=node4

node1.random=node4
node2.random=node1
node3.random=node2
node4.random=node3

print("Original List with node values:",node1.val,node2.val,node3.val,node4.val)
print("Original List with random node values:",node1.random.val,node2.random.val,node3.random.val,node4.random.val)
newHead=cloneLinkedList(head)
print("Cloned List with values of the nodes:",newHead.next.val,newHead.next.next.val,newHead.next.next.next.val,newHead.next.next.next.next.val)
print("Cloned List with values of the random nodes:",newHead.next.random.val,newHead.next.next.random.val,newHead.next.next.next.random.val,newHead.next.next.next.next.random.val)

w4p1.py: Solution for the first problem with O(n) space and time complexity.
w4p2a.py: Solution for the second problem with O(n) space and time complexity.
w4p2b.py: Solution for the second problem with O(1) space and O(n) time complexity.

*The struct (class) has been modified to include an attribute "value" only to easily identify the node and verify the results.