Daily Coding Problem - 26

day-26.py

"""
This problem was asked by Google.

Given a singly linked list and an integer k, remove the kth last element from the list. k is guaranteed to be smaller than the length of the list.

The list is very long, so making more than one pass is prohibitively expensive.

Do this in constant space and in one pass.
"""
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        if self.head is None:
            self.head = Node(val)
            return
        curr = self.head
        while curr.next is not None:
            curr = curr.next
        curr.next = Node(val)

    def printList(self):
        curr = self.head
        while curr is not None:
            print(curr.val, end='->')
            curr = curr.next
        print('None')

def getKlast(linkedlist, k):
    # pops the kth last element out from linked list
    fast_pointer = linkedlist.head
    slow_pointer = linkedlist.head
    for i in range(0, k):
        fast_pointer = fast_pointer.next
    # Now slow_pointer is k steps behind fast_pointer
    while fast_pointer.next is not None:
        fast_pointer = fast_pointer.next
        slow_pointer = slow_pointer.next
    kElement = slow_pointer.next
    slow_pointer.next = slow_pointer.next.next
    return kElement.val

my_list = LinkedList()
my_list.append(1)
my_list.append(2)
my_list.append(3)
my_list.append(4)
my_list.append(5)
my_list.printList()
print(getKlast(my_list, 2)) # 4
my_list.printList()