In [10]:
# Imports
import unittest
import random
import operator
import itertools
In [11]:
# Linked List Class
class LinkedList(object):
def __init__(self, value=None, head=None, tail=None):
self.head = head
self.tail = tail
self.value = value
def __str__(self):
return str((self.head.value if self.head is not None else None,
self.value,
self.tail.value if self.tail is not None else None,
))
def to_list(self):
current = self
values = []
while current and current.value is not None:
values.append(current.value)
current = current.tail
return values
def generate(values):
current = head = LinkedList()
for value in values:
current.value = value
current.tail = LinkedList()
current.tail.head = current
current = current.tail
current.head.tail = None
return head
In [12]:
# 2.1 - Remove Dups
def remove_dups(linkedList):
seen = set()
current = linkedList
while current:
if current.value not in seen:
seen.add(current.value)
else:
# Don't have to check if there is a head or not
# because this code will never execute for the
# first item in the list. There will always
# be a head.
current.head.tail = current.tail # One way LL
if current.tail is not None:
current.tail.head = current.head # Two way LL
current = current.tail
return linkedList
class Test(unittest.TestCase):
def test(self):
num = 10
linkedList = generate(range(num) * 2)
self.assertListEqual(remove_dups(linkedList).to_list(), range(num))
unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))
Out[12]:
In [13]:
# 2.2 - Return Kth to Last (Singly linked list)
def return_kth_to_last(linkedList, k):
endPointer = linkedList
kthPointer = linkedList
for i in range(k-1):
endPointer = endPointer.tail
if endPointer.tail is None:
raise RuntimeError('k is greater than the linked list length (%i>%i)' % (k, i))
while endPointer.tail is not None:
endPointer = endPointer.tail
kthPointer = kthPointer.tail
return kthPointer
class Test(unittest.TestCase):
def test1(self):
k = 5
num = 10
linkedList = generate(range(num))
self.assertListEqual(return_kth_to_last(linkedList, k).to_list(), range(k, num))
def test2(self):
k = 1
num = 10
linkedList = generate(range(num))
self.assertListEqual(return_kth_to_last(linkedList, k).to_list(), range(num-k, num))
unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))
Out[13]:
In [14]:
# 2.3 - Remove Middle Node (Singly linked list)
def remove_middle_node(node):
node.value = node.tail.value
node.tail = node.tail.tail
class Test(unittest.TestCase):
def test_first(self):
num = 10
n = 1
linkedList = current = generate(range(num))
for i in range(n):
current = current.tail
remove_middle_node(current)
self.assertListEqual(linkedList.to_list(), range(n)+range(n+1, num))
def test_middle(self):
num = 10
n = num/2
linkedList = current = generate(range(num))
for i in range(n):
current = current.tail
remove_middle_node(current)
self.assertListEqual(linkedList.to_list(), range(n)+range(n+1, num))
def test_last(self):
num = 10
n = num-2
linkedList = current = generate(range(num))
for i in range(n):
current = current.tail
remove_middle_node(current)
self.assertListEqual(linkedList.to_list(), range(n)+range(n+1, num))
unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))
Out[14]:
In [15]:
# 2.4 - Partition
def partition(linkedList, x):
""" Solution: Use a head and a tail pointer. Flip the
tail and head pointer's references when a value >= x
is found. """
p1 = linkedList
p2 = linkedList
while p1 and p2:
while p1.tail and p1.value >= x:
p1 = p1.tail
if p1 is not None:
# Swap all values
p1.value, p2.value = p2.value, p1.value
# Increment the pointers
p1 = p1.tail
p2 = p2.tail
return linkedList
class Test(unittest.TestCase):
def test(self):
num = 10
# Run 1000 tests
for _ in range(1000):
# Generate random input
nums = random.sample(range(num), num)
linkedList = generate(nums)
x = random.randint(0, num)
l = partition(linkedList, x).to_list()
# All values < x should be left of values >= x
first = num
for i, v in enumerate(l):
if v >= x:
first = i
break
self.assertTrue(all(z < x for z in l[:first]))
self.assertTrue(all(z >= x for z in l[first:]))
unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))
Out[15]:
In [16]:
# 2.5 - Sum 2 Linked Lists
from operator import add, mul
from itertools import starmap
def sum_lists(p1, p2):
""" Solution: Go through each value, add them together,
increment the 10s counter, and create a linked list
from the result."""
ll = first = None
while p1 or p2:
p1_value = p1.value if p1 else 0
p2_value = p2.value if p2 else 0
value = p1_value + p2_value
if ll is None:
ll = first = LinkedList(value)
else:
ll.tail = LinkedList(value)
ll = ll.tail
if p1: p1 = p1.tail
if p2: p2 = p2.tail
return first
class Test(unittest.TestCase):
def test(self):
# Run 1000 tests
for _ in range(1000):
# Generate random input
num1 = random.randint(2, 7)
num2 = random.randint(2, 7)
v1 = random.sample(range(num1), num1)
v2 = random.sample(range(num2), num2)
ll1 = generate(v1)
ll2 = generate(v2)
# Run the algorithm
llSum = sum_lists(ll1, ll2).to_list()
# The sum of the generated lists should equal
# the sum of the linked lists.
maxLength = max(len(v1), len(v2)) # Add zeros
v1 += [0]*(maxLength-len(v1))
v2 += [0]*(maxLength-len(v2))
truth = list(starmap(add, zip(v1, v2)))
# Run the test
self.assertListEqual(llSum, truth)
unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))
Out[16]:
In [17]:
# 2.6 - Palindrome
def _is_palindrome(ll, stack=None, level=0):
""" I think I can do this better. You just have to iterate through the
linked list until the end and do the first/last pop thing at the end.
It's O(n) time but also O(n) extra memory. """
# Make the stack if we haven't already
if stack is None:
stack = []
# If we are at the end of the linked list,
# return the size
if ll is None:
return stack
# Add the value to the stack
stack.append(ll.value)
# Recurse while incrementing the linked list and size
stack = _is_palindrome(ll.tail, stack, level+1)
# If we haven't gone all the way up yet, return
# the stack.
if level > 0:
return stack
# Now that the size and stack is populated,
# figure out if it's a palindrome
result = True
while stack and len(stack) > 1:
# Pop off the first and last items from the stack
first, second = stack.pop(0), stack.pop()
# Compare them
result &= (first == second)
return result
def is_palindrome(ll):
return _is_palindrome(ll) is not False
class Test(unittest.TestCase):
def test(self):
self.assertTrue(is_palindrome(generate(['a'])))
self.assertTrue(is_palindrome(generate(['a', 'a'])))
self.assertTrue(is_palindrome(generate(['a', 'a', 'a'])))
self.assertTrue(is_palindrome(generate(['a', 'b', 'c', 'b', 'a'])))
self.assertFalse(is_palindrome(generate(['a', 'b', 'c', 'z', 'a'])))
self.assertFalse(is_palindrome(generate(['a', 'b'])))
unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))
Out[17]:
In [18]:
# 2.8 - Loop Detection
""" Return node at beginning of loop, not a node in the loop,
or a boolean, but the node at the beginning of the loop! """
""" This is not the correct way to do it."""
def find_loop_start(ll):
""" Ideas:
1. Remove loop from list then iterate through again and return the ending node.
2. Instead of removing completely, move them to a new linked list so I can copy
it back after figuring out wher ethe first node of the loop is.
"""
# Find the loop and remove it from the linked list
fast = ll
slow = ll
print ''
loopFound = False
while fast.tail and fast.tail.tail and slow.tail:
print fast.value, slow.value
fast = fast.tail.tail
slow = slow.tail
if fast.value == slow.value:
loopFound = True
break
if not loopFound:
raise RuntimeError("Loop not detected")
# Copy the loop to a new linked list
print 'loop found', fast.value, slow.value
return ll
class Test(unittest.TestCase):
def test_loop_even_small(self):
first = ll = generate(range(1, 4))
while ll.tail:
ll = ll.tail
endOfLinear = ll
print 'linear part', first.to_list()
print 'endOfLinear', endOfLinear.value
endOfLinear.tail = generate(range(6, 20))
ll = endOfLinear.tail
i = 0
while ll.tail and i < 100:
print ll.value,
ll = ll.tail
print ll.value
ll.tail = endOfLinear.tail
a = find_loop_start(first).value
b = endOfLinear.tail.value
print 'returned value', a
print 'start of loop value', b
self.assertEqual(a, b)
unittest.TextTestRunner().run(unittest.TestLoader().loadTestsFromTestCase(Test))
Out[18]: