Find kth node from end of the linked list in C

To find kth node from end of the linked list

Find kth Node from end of the linked list in C ,We know that in singly linked list traversal is done through front only. so we will count the element from front to end of the linked list and we will find the position from front to last. when we find the position of the element then we get the node.

We can solve this problem in one traversal only.The idea is start from the head node to move a pointer K nodes ahead  in given list.

Find kth Node from end of the linked list in C

Working for finding the kth node:-

  1. First take the input in the list.
  2. Initially PTR -> HEAD (pointer is the head of the linked list).
  3. Then PTR=NULL (we need to find kth from the end of the linked list).
  4. When k=3 means the last third element of the linked list.
  5. After that print it.
C Program Find kth node from end of the linked list

Structure of the node in the Singly Linked List:-

struct node
{
int data;
struct node *next;
};

To study more Click below :-

Find kth Node from end of the linked list in C:-

#include <stdio.h> 		//header files
#include <stdlib.h> 		//library files

	 // Data Structure to store a linked list node
struct Node
{
  int data;
  struct Node *next;
};

      // Iterative function to return K'th node from the end in a linked list
struct Node *getKthFromtheEnd (struct Node *head, int k)
{
  struct Node *temp = head;
  int n = 0;


// Count number of nodes in the linked list
  while (temp)
    {
      temp = temp->next;
      n++;
    }

// if number of nodes is more than or equal to K
  if (n >= k)
    {
// return (n-k+1)th node from the beginning
      temp = head;
      for (int i = 0; i < n - k; i++) temp = temp->next;
    }

   return temp;
}

// function for create a new Node with the given data and
// pushes it onto the front of the list

void push (struct Node **head, int data)
{
// create a new linked list node from heap
  struct Node *newNode = (struct Node *) malloc (sizeof (struct Node));

  newNode->data = data;
  newNode->next = *head;
  *head = newNode;
}

// main method
int main (void)
{
// given input keys
  int keys[] = { 1, 2, 3, 4, 5 };
  int n = sizeof (keys) / sizeof (keys[0]);

  struct Node *head = NULL;
  for (int i = n - 1; i >= 0; i--)
    push (&head, keys[i]);

  int k = 3;
  struct Node *node = getKthFromtheEnd (head, k);

  if (node)
    printf ("K'th node from the end is %d", node->data);

  return 0;
}
Output:-
K'th node from the end is 3