Find kth node from the end

© 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