Copy List with Random Pointer Python

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

Return a deep copy of the 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) where random pointer points to, or null if it does not point to any node.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

• -10000 <= Node.val <= 10000
• Node.random is null or pointing to a node in the linked list.
• Number of Nodes will not exceed 1000

"""

# Definition for a Node.

class Node:

    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):

        self.val = int(x)

        self.next = next

        self.random = random

"""

class Solution:        

    def copyRandomList(self,head):

        if not head:

            return head

        ptr = head

        while ptr:

            new_node = Node(ptr.val,None,None)

            new_node.next = ptr.next

            ptr.next = new_node

            ptr = new_node.next

            

        ptr = head

        

        while ptr:

            new_node = ptr.next

            new_node.random = ptr.random.next if ptr.random else None

            ptr = new_node.next

            

        old_ptr = head

        new_ptr = head.next

        final_ptr = head.next

        while old_ptr:

            old_ptr.next = old_ptr.next.next if old_ptr.next else None

            new_ptr.next = new_ptr.next.next if new_ptr.next else None

            old_ptr = old_ptr.next

            new_ptr = new_ptr.next

            

        return final_ptr

Time Complexity : O(n)

Space Complexity :O(1)

            

        

            

            

        

            

        

        

        

        

        

        

        

        

Copy List with Random Pointer Python

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

Return a deep copy of the 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) where random pointer points to, or null if it does not point to any node.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

• -10000 <= Node.val <= 10000
• Node.random is null or pointing to a node in the linked list.
• Number of Nodes will not exceed 1000.

"""

# Definition for a Node.

class Node:

    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):

        self.val = int(x)

        self.next = next

        self.random = random

"""

class Solution:

    def __init__(self):

        self.visited = {}

    

    def getclonedNode(self,node):

        if node:

            if node in self.visited:

                return self.visited[node]

            else:

                self.visited[node] = Node(node.val,None,None)

                return self.visited[node]

        return None

        

        

        

    def copyRandomList(self,head):

        if not head:

            return head

        old_node = head

        new_node = self.getclonedNode(old_node)

        

        while old_node != None:

            new_node.next = self.getclonedNode(old_node.next)

            new_node.random = self.getclonedNode(old_node.random)

            

            new_node = new_node.next

            old_node = old_node.next

        return self.visited[head]

        

        

        

       Time Complexity : O(n)

       Space Complexity : O(n)

Intersection of Two Linked Lists Python

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

class Solution:    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:        if not headA or not headB:            return None                hA = headA

        hB = headB

                while hA is not hB:            hA = headB if hA is None else hA.next            hB = headA if hB is None else hB.next

Time Complexity : O(n)

Space Complexity : O(1)

                    return hA

Intersection of Two Linked Lists Python

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:

        lA , lB = 0,0

        hA , hB = headA,headB

        if not hA or not hB:

            return None

        while hA != None:

            lA+=1

            hA = hA.next

        while hB != None:

            lB+=1

            hB=hB.next

        hA ,hB = headA,headB

        if lA > lB:

            k = lA-lB

            while k > 0:

                hA = hA.next

                k -=1

        elif lB > lA:

            k = lB-lA

            while k > 0:

                hB = hB.next

                k -=1

        while hA != hB:

            hA =hA.next

            hB =hB.next

        return hA

                

            

      Time Complexity : O(n)

      Space Complexity : O(1)

Find Median from Data Stream Python

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,

[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

Follow up:

1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

class MedianFinder:

    def __init__(self):

        """

        initialize your data structure here.

        """

        self.small_heap = [ ] 

        self.large_heap = [ ] 

        

        

    def addNum(self, num: int) -> None:

        if len(self.small_heap) == len(self.large_heap):

            heappush(self.small_heap,-heappushpop(self.large_heap,num))

        else:

            heappush(self.large_heap,-heappushpop(self.small_heap,-num))

        

        

        

    def findMedian(self) -> float:

        if len(self.small_heap) == len(self.large_heap):

            return (float)(self.large_heap[0] - self.small_heap[0]) / 2

        else:

            return (float)(-self.small_heap[0])

        

        

# Your MedianFinder object will be instantiated and called as such:

# obj = MedianFinder()

# obj.addNum(num)

# param_2 = obj.findMedian()

// Time Complexity : O(logn)

//Space Complexity: O(n)