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:

1. Initialize Two Pointers: Start with two pointers, first and second, both set to the head of the list.
2. Move First Pointer: Move the first pointer K steps forward.
3. Move Both Pointers: Move both pointers one step at a time until the first pointer reaches the end of the list.
4. 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.