``````

In [143]:

class LLNode:
def __init__(self, value):
self.next = None
self.value = value

def __str__(self):
node = self
while node != None:
string = "{0} {1}".format(string, node.value)
node = node.next
return string

def append(self, value):
node = self
while node.next != None:
node = node.next
node.next = LLNode(value)

if curr.value == value:
curr = None

while curr.next != None:
if curr.next.value == value:
curr.next = curr.next.next
curr = curr.next

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

In [144]:

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

Linked List: 1 2 3 2

``````

2.1

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 [145]:

nodes_seen = set()
prev = None
while curr != None:
if curr.value in nodes_seen:
prev.next = curr.next
else:
prev = curr
curr = curr.next

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

In [146]:

llist = LLNode(1)
llist.append(4)
llist.append(5)
llist.append(5)
llist.append(5)
llist.append(1)
llist.append(6)
llist.append(5)
llist.append(3)
print(llist)
remove_duplicates(llist)
print(llist)

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

Linked List: 1 4 5 5 5 1 6 5 3
Linked List: 1 4 5 6 3

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

In [147]:

while curr != None:
else:
curr = curr.next

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

In [148]:

llist = LLNode(1)
llist.append(4)
llist.append(5)
llist.append(5)
llist.append(5)
llist.append(1)
llist.append(6)
llist.append(5)
llist.append(3)
print(llist)
remove_duplicates_followup(llist)
print(llist)

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

Linked List: 1 4 5 5 5 1 6 5 3
Linked List: 1 4 5 6 3

``````

2.2

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

``````

In [149]:

if k < 0:
return None
for i in range(1, k):
if runner == None:
if i == k:
return curr
else:
return None
runner = runner.next
while runner != None:
curr, runner = curr.next, runner.next
return curr

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

In [150]:

llist = LLNode(1)
llist.append(4)
llist.append(5)
llist.append(5)
llist.append(5)
llist.append(1)
llist.append(6)
llist.append(5)
llist.append(3)
print(llist)
node = find_kth_last(llist, 3)
print(node)

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

Linked List: 1 4 5 5 5 1 6 5 3

``````

2.3

Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.

EXAMPLE

Input: the node c from the linked list a->b->c->d->e

Result: nothing is returned but the new linked list looks like a->b->d->e

``````

In [151]:

def remove_from_middle(node):
if (node == None) or (node.next == None):
return False
node.value = node.next.value
node.next = node.next.next

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

In [152]:

llist = LLNode(1)
llist.append(4)
llist.append(5)
llist.append(5)
llist.append(5)
llist.append(1)
llist.append(6)
llist.append(5)
llist.append(3)
print(llist)
node = llist.next.next.next.next.next
print(node)
remove_from_middle(node)
print(llist)

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

Linked List: 1 4 5 5 5 1 6 5 3
Linked List: 1 6 5 3
Linked List: 1 4 5 5 5 6 5 3

``````