Find Kth element from end in Linked List


Category: Data Structure And Algorithms Tags: C#

Write a program to find Kth element from end in a given linked list. Suppose linked list is as below:

Head -> 1 -> 2 -> 3 -> 4 -> 5

And K = 2

Output

2nd node from end is: 4


Like 0 People
Asked on 14 June 2021
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 146
Questions: 16
Given Best Solutions: 16 *

Answers:

Nikhil Joshi

We can solve this problem by keeping two pointers. First pointer starts at head and another pointer called forward pointer which is already forwarded to Kth node from head. So when we traverse the linked list we forward each pointer by one node thus first pointer always be behind kth position from forward pointer. Once forward pointer reaches to end first pointer will give us Kth element from end. Look at the code below.

static Node KthNodeFromEnd(Node head, int k)
{
    Node temp = head;
    Node forwardPointer = head;

    //Making forward pointer Kth position ahead of temp
    while (k > 1)
    {
        if (forwardPointer.Next != null)
            forwardPointer = forwardPointer.Next;
        else
            throw new OverflowException($"Linked list size is less than {k}");
        k--;
    }

    //Traversing forward pointer to the end
    while (forwardPointer.Next != null)
    {
        forwardPointer = forwardPointer.Next;
        temp = temp.Next;
    }
    return temp;
}

Let's run above code.

static void Main(string[] args)
{
    int k = 2;
    Node head = new Node(1);
    head.Next = new Node(2);
    head.Next.Next = new Node(3);
    head.Next.Next.Next = new Node(4);
    head.Next.Next.Next.Next = new Node(5);

    Node kthNodeFromEnd = KthNodeFromEnd(head, k);

    Console.WriteLine($"{k}th node from end is: " + kthNodeFromEnd.Value);
}

Output

2th node from end is: 4

Like 0 People on 14 June 2021

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x