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

CareerCup2.2.py

"""
 ============================================================================
 Question        : 2.2 Implement an algorithm to find the kth to last element of a singly linked list.
 Solution        : Faster pointer move forward Kth node first, then move forward to the end alone with slow pointer,
                   until faster pointer reaches the end, return slower pointer
 Time Complexity : O(N)
 Space Complexity: O(1)
 Gist Link       : https://gist.github.com/habina/f521508cef301ac0d18d
 ============================================================================
"""
import random

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

    def __str__(self):
        return chr(self.value)

def print_linkedList(node):
    while node:
        print(node)
        node = node.next
    print

def initialize_linkedList(n):
    random.seed()
    head = Node(random.randint(97, 122), 0)
    n -= 1
    current = head
    while(n > 0):
        temp = Node(random.randint(97, 122), 0)
        current.next = temp
        current = temp
        n -= 1
    return head

def find_kth_to_end(head, k):
    fast = head
    slow = head
    for i in range(k):
        if(fast.next):
            fast = fast.next
        else:
            print("nodes are less than k")
            return 0
    while(fast):
        fast = fast.next
        slow = slow.next
    return slow

total_node = 10
a = initialize_linkedList(total_node)
print("Original Linked List:")
print_linkedList(a)
print()
k = 8
b = find_kth_to_end(a, k)
if(b):
    print("Linked List %dth to end:", k)
print_linkedList(b)