``````

In [1]:

class Node():
def __init__(self, value, Next=None):
self.value = value
self.next = Next
def __str__(self):
if self.next == None:
return str(self.value)
return str(self.value) + '-' + self.next.__str__()

``````
``````

In [12]:

def getSize(node):
count = 0
while node != None:
count += 1
node = node.next
return count

if node0 == None:
return None, 0

if size0 > size1:
node, carry = _add(node0.next, size0 - 1, node1, size1)

new = node0.value + carry
else:
node, carry = _add(node0.next, size0 - 1, node1.next, size1 -1)

new = node0.value + node1.value + carry

carry = new//10
new = new%10
print(new, carry)
return Node(new, node), carry

node, carry = _add(node0, size0, node1, size1)
if carry > 0:
node = Node(1, node)

return node

a = Node(1, Node(2, Node(5, Node(6, Node(3, None)))))
b = Node(8, Node(4, Node(2, None)))

``````
``````

5 0
0 1
4 1
3 0
1 0
1-3-4-0-5

``````

## 2.1 Remove Dups:

Write code to remove duplicates from an unsorted linked list. FOLLOW UP How would you solve this problem if a temporary buffer is not allowed?

``````

In [24]:

List = Node(1, Node(2, Node(3, Node(4, Node(4, Node(4, Node(3, Node(2, Node(1)))))))))

def remove_dups(List):
marks = {}
cur = List
prev = None
while cur != None:
if marks.get(cur.value, 0) == 0: # not duplicated
marks[cur.value] = 1
else: # duplicated
prev.next = cur.next
cur = prev

prev = cur
cur = cur.next

print('input:' + str(List))
remove_dups(List)
print('output:' + str(List))

``````
``````

input:1-2-3-4-4-4-3-2-1
output:1-2-3-4

``````
``````

In [34]:

def remove_dups_wo_buffer(List):
cur0 = List
while cur0 != None:
prev = cur0
cur1 = cur0.next
while cur1 != None:
if cur1.value == cur0.value:
prev.next = cur1.next
cur1 = prev
prev = cur1
cur1 = cur1.next

cur0 = cur0.next

List = Node(1, Node(2, Node(3, Node(4, Node(4, Node(4, Node(3, Node(2, Node(1, Node(3, Node(2)))))))))))

print('input:' + str(List))
remove_dups_wo_buffer(List)
print('output:' + str(List))

``````
``````

input:1-2-3-4-4-4-3-2-1-3-2
output:1-2-3-4

``````

## 2.2 Return Kth to Last:

Implement an algorithm to find the kth to last element of a singly linked list.

``````

In [37]:

List = Node(1, Node(2, Node(3, Node(4, Node(4, Node(4, Node(3, Node(2, Node(1, Node(3, Node(2)))))))))))

def kth_to_last(List, k):
cur = List
size = 0
while cur != None:
size += 1
cur = cur.next
if size < k:
return None

cur = List
for _ in range(size - k):
cur = cur.next
return cur.value

print(kth_to_last(List, 4))

``````
``````

2

``````
``````

In [40]:

return None

i[0] = i[0] + 1
if i[0] == k:
else:
return node

print(kth_to_last(List, 4, [0]))

``````
``````

2-1-3-2

``````
``````

In [ ]:

``````