blob: 0ef176daebb3ea9752ab99d6cd4009f06bf64982 (
plain)
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
|
# 707. Design Linked List
"""
design your implementation of the linked list. you can choose to use a singly
or doubly linked list. a node in a singly linked list should have two
attributes: 'val' and 'next'. 'val' is the value of the current node, and
'next' is a pointing/reference to the next code. if you want to use the
doubly linked list, you will need one more attribute 'prev' to indicate the
previous node in the linked list. assume all nodes in the linked list are
0-indexed to indicate the previous node in the linked list. assume all nodes
in the linked list are 0-indexed.
"""
class Node(object):
def __init__(self, val):
self.val = val
self.next = None
class MyLinkedList(object):
def __init__(self):
self.head = None
self.size = 0
def get(self, index):
"""
:type index: int
:rtype: int
"""
if index < 0 or index >= self.size:
return -1
if self.head is None:
return -1
curr = self.head
for i in range(index):
curr = curr.next
return curr.val
def addAtHead(self, val):
"""
:type val: int
:rtype: None
"""
node = Node(val)
node.next = self.head
self.head = node
self.size += 1
def addAtTail(self, val):
"""
:type val: int
:rtype: None
"""
curr = self.head
if curr is None:
self.head = Node(val)
else:
while curr.next is not None:
curr = curr.next
curr.next = Node(val)
self.size += 1
def addAtIndex(self, index, val):
"""
:type index: int
:type val: int
:rtype: None
"""
if index < 0 or index > self.size:
return
if index == 0:
self.addAtHead(val)
else:
curr = self.head
for i in range(index - 1):
curr = curr.next
node = Node(val)
node.next = curr.next
curr.next = node
self.size += 1
def deleteAtIndex(self, index):
"""
:type index: int
:rtype: None
"""
if index < 0 or index >= self.size:
return
curr = self.head
if index == 0:
self.head = curr.next
else:
for i in range(index - 1):
curr = curr.next
curr.next = curr.next.next
self.size -= 1
if __name__ == "__main__":
obj = MyLinkedList()
obj.addAtHead(1)
obj.addAtTail(3)
obj.addAtIndex(1, 2)
print(obj.get(1))
obj.deleteAtIndex(1)
print(obj.get(1))
|