Algorithm

Last Kth Node of Linked List

Nicholas Wong

Nicholas Wong

— 1 min read
Last Kth Node of Linked List

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

Read more