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):
            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.assertRaises(AttributeError, get_kth_to_last_node, Test.a_list, 5)
if __name__ == '__main__':