Program to find Kth node from the end of Linked List - Programmer's Mind

To find the K^th node from the end of linked list  two pointer approach can be used which involves four steps. Consider a linked list which contains 6 nodes with the values 1,2,3,4,5,6 as shown below and let the k be 3.

Initialize two pointers (head,temp) at the first node

Take two pointers (head, temp) and initialize them at the first node.

Move first pointer to the K^th node 

Lets move temp pointer to the K^th node from the beginning, so that head becomes the K^th node from temp. In the example, move temp to 3rd node so that 1 becomes 3rd node from the temp.

Move both pointers by a node until temp pointer reaches the last node

Now move both the pointer by one node.So that temp will be at node with value 4 and head will be at node with value 2.

Repeat this until temp pointer reaches end of the linked list. so that position of pointers will be as follows

Return second node 

Now return the node which is at head pointer and this will be the K^th node from the end of linked list.

Program to find K^th node from the end of the Linked List

void kthNodeFromEnd(struct node *head, int k) {
  struct node *temp = head;
  int i;
  for (i = 1; i < k; i++) {
    if (temp == NULL) {
      printf("%d is greater than length of the list", k);
      return;
    }
    temp = temp -> next;
  }
  while (temp -> next != NULL) {
    temp = temp -> next;
    head = head -> next;
  }
  printf("kth element from the end of the given List is %d", head -> data);
  return;
}

Share on Google Plus