2.2 Return Kth to Last – CCI

  • Initialize two pointers
  • Advance a fast pointer k times
  • then advance both pointers until fast pointer is at the last node
  • return node at slow pointer
# [2.2] Return Kth to Last: Implement an algorithm to find
# the kth to last element of a singly linked list.

# Space complexity: O(1)
# Time complexity: O(N)

import unittest

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

def get_kth_to_last_node(node, k):
    fast = node
    slow = node

    for i in xrange(k):
        try:
            fast = fast.next
        except AttributeError:
            raise Exception('k must be smaller than length of list - 1')

    while fast.next:
        fast = fast.next
        slow = slow.next

    return slow

class Test(unittest.TestCase):

    a_list = Node(3,Node(5,Node(6,Node(10,Node(5)))))
    k = 2
    
    def test_get_kth_to_last_node(self):
        self.assertEqual(get_kth_to_last_node(Test.a_list,2).value,6)
        self.assertEqual(get_kth_to_last_node(Test.a_list,4).value,3)
        self.assertEqual(get_kth_to_last_node(Test.a_list,4).value,3)
        self.assertRaises(AttributeError, get_kth_to_last_node, Test.a_list, 5)
        
if __name__ == '__main__':
    unittest.main()