This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).
In [1]:
%run ../linked_list/linked_list.py
In [2]:
class MyLinkedList(LinkedList):
def kth_to_last_elem(self, k):
if self.head is None:
return
if k >= len(self):
return
curr = self.head
prev = self.head
counter = 0
# Give current a headstart, incrementing it
# once for k = 1, twice for k = 2, etc
while counter < k:
curr = curr.next
counter += 1
if curr is None:
return
# Increment both pointers until current reaches the end
while curr.next is not None:
curr = curr.next
prev = prev.next
return prev.data
In [3]:
%%writefile test_kth_to_last_elem.py
from nose.tools import assert_equal
class Test(object):
def test_kth_to_last_elem(self):
print('Test: Empty list')
linked_list = MyLinkedList(None)
assert_equal(linked_list.kth_to_last_elem(0), None)
print('Test: k >= len(list)')
assert_equal(linked_list.kth_to_last_elem(100), None)
print('Test: One element, k = 0')
head = Node(2)
linked_list = MyLinkedList(head)
assert_equal(linked_list.kth_to_last_elem(0), 2)
print('Test: General case')
linked_list.insert_to_front(1)
linked_list.insert_to_front(3)
linked_list.insert_to_front(5)
linked_list.insert_to_front(7)
assert_equal(linked_list.kth_to_last_elem(2), 3)
print('Success: test_kth_to_last_elem')
def main():
test = Test()
test.test_kth_to_last_elem()
if __name__ == '__main__':
main()
In [4]:
%run -i test_kth_to_last_elem.py