# Interview Questions

# k’th Node from End

- June 13, 2012
- Posted by: Kamal Rawat
- Category: Algorithms

Given a linked list and a positive integer k, write a function which will return value of k’th node from the end of list. If Linked list is

2 -> 4 -> 6 -> 3 -> 7

and k=2, then output should be 3 (2^{nd} node from end).

### Solution:

**Method-1: Brute force method:**

The brute force approach is to traverse the list twice. Calculate the total number of nodes in the first pass, say N, Now you have to print the (N-k)th node from the start of the list. Below function does this

node * findFromEnd(node * head, int k) { if(k<0 || !head) { return NULL; } node * val = NULL; int N = 0; /* Calculate the total number of nodes in list, * val is assigned head to avoid using another temporary object. * we cannot change head because we will loose a pointer to the first node */ // Empty loop for(val=head; val; val=val->link; N++); val = NULL; // Empty loop for(int i=0; i<N-k; i++) val = val->link; return val; }

**Method-2: Extra Pointer method:**

Maintain 2 pointers A & B both initialized to the head of the linked list. Move A ahead of B so that A points to the k’th element (from start of the list). Now move both the pointers ahead, one node at a time till A reaches the end of the list.

When A is at the end of the list B will be pointing to the k’th node from the end of the list.

**Code:**

node * findFromEnd(node * head, int k) { if(k<0 || ! head) return NULL; /* we will have only one pointer, head pointer will act as the second pointer */ node * A = NULL; for(int i=0; ilink); /* Case – list has less than k elements */ if(!A) return NULL; while(A->link) { A = A->link; head = head->link; } return head; }

Time Complexity of both the above methods is O(n), where n = number of nodes in the linked list.