# Find the Kth Node from the End in a Singly Linked List

## Finding the Kth Node from the End

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.

## Step-by-Step Process

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:

**Initialize Two Pointers**: Start with two pointers, first and second, both set to the head of the list.**Move First Pointer**: Move the first pointer K steps forward.**Move Both Pointers**: Move both pointers one step at a time until the first pointer reaches the end of the list.**Return the Second Pointer**: The second pointer will be at the Kth node from the end when the first pointer reaches the end.

After performing these steps, the second pointer will point to the Kth node from the end of the linked list.

## Python Program to Find the Kth Node from the End in a Singly 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.