You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Last Kth Node of Linked List

Nicholas Wong
Nicholas Wong

Question

Given a linked list, find the Kth last node in a linked list. The last 0th node is the tail node in the linked list.

Solution

Easy task. Construct 2 pointers: P1 and P2. First, both of them are set to head. Then move P2 to the next (K+1)th node. And then move both P1 and P2 until P2 hits the end.

Example

# node structure 
class Node: 
    def __init__(self, data, next=None): 
        self.data = data 
        self.next = next 

# get item 
def get_last(head, k): 
    pointer_1 = head 
    pointer_2 = head 
    for i in xrange(k+1): 
        if pointer_2 is not None: 
            pointer_2 = pointer_2.next 
    while pointer_2 is not None: 
        pointer_1 = pointer_1.next 
        pointer_2 = pointer_2.next 
    return pointer_1 
        
# linked list 
node_9 = Node(35) 
node_8 = Node(74, node_9) 
node_7 = Node(65, node_8) 
node_6 = Node(12, node_7) 
node_5 = Node(32, node_6) 
node_4 = Node(64, node_5) 
node_3 = Node(24, node_4) 
node_2 = Node(32, node_3) 
node_1 = Node(45, node_2) 
head = node_1 

# main 
print get_last(head, 0).data # should be 35
print get_last(head, 5).data # should be 64
print get_last(head, 8).data # should be 45
Algorithm

Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.