find the kth largest node in a linked list in python

To find the kth largest node in a linked list, we can use the following steps:

  1. Traverse the linked list to find the total number of nodes n in the list.
  2. Traverse again but stop at the (n-k)th node.
  3. Return the data value of the (n-k)th node.

Here is the sample code in Python:

main.py
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        
class LinkedList:
    def __init__(self):
        self.head = None
        
    def insert(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
        current_node.next = new_node
    
    def find_kth_largest(self, k):
        count = 0
        current_node = self.head
        while current_node is not None:
            count += 1
            current_node = current_node.next
        if k > count:
            return None
        current_node = self.head
        for i in range(count-k):
            current_node = current_node.next
        return current_node.data
871 chars
32 lines

To use this function, we can create a linked list and call the find_kth_largest function with the desired k value:

main.py
linked_list = LinkedList()
linked_list.insert(1)
linked_list.insert(3)
linked_list.insert(2)
linked_list.insert(5)
linked_list.insert(4)

print(linked_list.find_kth_largest(3)) # Output: 3
189 chars
9 lines

gistlibby LogSnag