Find the Kth node from the end in a singly linked list.

The main drawback of a singly linked list is that we can not iterate it from backward. So, finding a node from the end in the singly-linked list is not as easy as we thought.

First, we take a temporary node starting from the head and moves it to ‘K’ nodes from the head. Now take another node that begins at the head node, and now we move both nodes by jumping one by one until the temporary node reaches the end. If the first node reaches to end, then the second node reaches its (N-K) node.

Let us learn this with an example.

At start ‘current’ is at K distance from start. Now we will move one by one until current reaches end.
If the current reaches end of the linked list, K-th node reaches to 3rd from end node.

It is the only way to find a K-th node from the end with a single iteration. Let’s see the ‘C’ code for this approach.

int findKthNode(Node *head, int k)
{
    Node *curr = head;
    Node *kThNode = NULL;
    int cntr = 0;
    while (curr != NULL)
    {
        cntr++;
        if (cntr == k)
        {
            kThNode = head;
        }
        else if (cntr > k)
        {
            kThNode = kThNode->next;
        }
        curr = curr->next;
    }
    return kThNode->data;
}

As it runs in a single iteration, the runtime complexity of this approach is O(N). Let’s see the complete code with the main function.

// Output
10  14  7  3  10  3  7  8  14  
3rd node from end is: 7

It is one of the easiest ways to find the K-th node from the end in a singly linked list. If you know any better approach than this, please help our readers by commenting here below. Happy Learning!.

Advertisements