find the kth largest node in a linked list in csharp

One way to find the kth largest node in a linked list in C# is to make use of two pointers. The first pointer (let's call it "lead") will move k nodes ahead of the second pointer (let's call it "follower"). Once the first pointer reaches the end of the list, the second pointer will be at the kth last node in the list, which is the kth largest node.

Here's the C# code to implement this algorithm:

main.cs
public ListNode FindKthLargestNode(ListNode head, int k) {
    ListNode lead = head;
    ListNode follower = head;

    // Move the lead pointer k nodes ahead of the follower
    for (int i = 0; i < k; i++) {
        if (lead == null) {
            throw new ArgumentException("Linked list has less than k nodes");
        }
        lead = lead.Next;
    }

    // Move both pointers until the lead pointer reaches the end of the list
    while (lead != null) {
        lead = lead.Next;
        follower = follower.Next;
    }

    return follower;
}
552 chars
21 lines

Assuming ListNode is a class representing a node in the linked list, with a Next property pointing to the next node in the list, you can use this method like this:

main.cs
ListNode head = new ListNode(1);
head.Next = new ListNode(3);
head.Next.Next = new ListNode(2);
head.Next.Next.Next = new ListNode(5);
head.Next.Next.Next.Next = new ListNode(4);

ListNode kthLargest = FindKthLargestNode(head, 3);
Console.WriteLine(kthLargest.Value); // Outputs 3
281 chars
9 lines

gistlibby LogSnag