© Parineeth M R

** Question 3. Find the kth node from the end of a linked list**

We can treat the last node in the linked list as either the 0th node from the end or we can treat the last node as the 1st node from the end. So k can begin from 0 or 1. In the function below, we are treating the last node as the 1st node from the end. To find the kth node from the end, we first find the length of the linked list. Then we again traverse through the linked list to find the (length – k +1)th node from the beginning which corresponds to the kth node from the end. If the length of the linked list is n, then in the worst case we will access 2n nodes. The time complexity is O(n)

## C/C++

/* head: first node of the linked list k: node position from the end. k starts from 1 onwards Return value: kth node from end if it exists, NULL otherwise */ struct node* find_kth_node_from_end(struct node *head, int k) { struct node *n1; int i, length; length = 0; n1 = head; while (n1 != NULL) { length++; n1 = n1->next; } n1 = head; for (i = 1; i <= length; ++i) { if (i == length - k + 1) { return n1; /*n1 is the kth node from end. So return it*/ } n1 = n1->next; } /*k value passed doesn't match with the linked list. So return NULL */ return NULL; }

## Java

/* head: the first node of the linked list k: node position from the end. k starts from 1 onwards Return value: kth node from end if it exists, null otherwise */ public static LinkedListNode findKthNodeFromEnd(LinkedListNode head, int k) { int length = 0; LinkedListNode n1 = head; while (n1 != null) { length++; n1 = n1.next; } n1 = head; for (int i = 1; i <= length; ++i) { if (i == length - k + 1) { return n1; /*n1 is the kth node from end. So return it*/ } n1 = n1.next; } /*k value passed doesn't match with the linked list. So return null */ return null; }

## Python

#head: the first node of the linked list #k: node position from the end. k starts from 1 onwards #Return value: kth node from end if it exists, None otherwise @staticmethod def find_kth_node_from_end(head, k): length = 0 n1 = head while (n1): length += 1 n1 = n1.next n1 = head for i in range(1, length + 1): if (i == length - k + 1): return n1 #n1 is the kth node from end. So return it n1 = n1.next #k value passed doesn't match with the linked list. So return None return None