ds_algo/queue_ll.py at master · joshi95/ds_algo · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = front
        self.size = 0

    def push(self, x):
        if self.front is None:
            self.front = Node(x)
            self.rear = self.front
        else:
            self.rear.next = Node(x)
            self.rear = self.rear.next
        self.size += 1

    def pop(self):
        x = self.front.val
        self.front = self.front.next
        self.size -= 1
        return x

    def get_size(self):
        return self.size

front = Node(5)
rear = front


class DoublyLinkedListNode:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

head = DoublyLinkedListNode(5)
node = DoublyLinkedListNode(15)
head.next = node
node.prev = head


############
# cloning a singly linked list
######

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


def clone(head):
    # returns a cloned linked list

    cur = head
    cloned_linked_list_head = None
    prev = None
    while cur != None:
        if cloned_linked_list_head is None:
            cloned_linked_list_head = Node(cur.val)
            prev = cloned_linked_list_head
        else:
            prev.next = Node(cur.val)
            prev = prev.next
        cur = cur.next
    return cloned_linked_list_head


head = Node(1)
head.next = Node(5)
head.next.next = Node(10)

new_head = clone(head)


# Leetcode

#
"""
# 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: 'Node') -> 'Node':
        mapping = dict()
        cur = head


        cur = head
        cloned_linked_list_head = None
        prev = None
        while cur != None:
            n = Node(cur.val)
            mapping[cur] = n
            if cloned_linked_list_head is None:
                cloned_linked_list_head = n
                prev = cloned_linked_list_head
            else:
                prev.next = n
                prev = prev.next
            cur = cur.next


        cur = head

        while cur != None:
            x = mapping[cur]
            if cur.random is not None:
                y = mapping[cur.random]
                x.random = y
            cur = cur.next

        return cloned_linked_list_head