Finding the Kth node from the end in a singly linked list involves determining the node that is K positions from the end of the list. This can be efficiently achieved using the two-pointer technique.
Consider a singly linked list with the following structure:
Head -> 1 -> 2 -> 3 -> 4 -> 5 -> None
To find the Kth node from the end in this list, follow these steps:
After performing these steps, the second pointer will point to the Kth node from the end of the linked list.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
def find_kth_from_end(self, k):
first = self.head
second = self.head
for _ in range(k):
if first is None:
return None # k is greater than the length of the list
first = first.next
while first:
first = first.next
second = second.next
return second
def traverse(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Example usage:
linked_list = SinglyLinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)
linked_list.append(5)
print("Linked list:")
linked_list.traverse() # Output: 1 -> 2 -> 3 -> 4 -> 5 -> None
k = 2
kth_node = linked_list.find_kth_from_end(k)
if kth_node:
print(f"{k}th node from end: {kth_node.data}") # Output: 4
else:
print(f"The list is shorter than {k} nodes.")
This Python program defines a singly linked list with methods for appending nodes, finding the Kth node from the end using the two-pointer technique, and traversing the list. The find_kth_from_end method returns the Kth node from the end of the list.