Kth largest number in linked List

25 Likes Comment

Here, today we are going to find the Nth largest number in a linked list.

We will be solving it with the help of a two step strategy

  1. Sort the Linked List.
  2. Traverse to the nth element.

For sorting, we can use any of the sorting techniques. For illustration, we will choose merge sort.

1.Merge sort

Always keep this figure in mind while working with the merge sort. First we will split the linked into two halves and sort them. Then we repeat this process in the two halves and keep sorting each halve. As we are dividing our problem into sub problems and then solving it, thus it is a divide and conquer problem.

Pseudo code for merge sort

Code for merge sort

You can also see other sorting techniques from here.

2.Traversing

Now we got the sorted linked list in ascending order. Thus

n-1 th element will be the largest

n-2 th element will be the 2nd largest

. . . . . . .

. . . . . . .

n-kth element will be the kth largest.

Traversal code

NOTE – You can also sort in descending order and then call the 1st element as largest, 2nd as 2nd largest and thus kth as kth largest element.

Combining these two sorting and traversing, you can easily get the kth largest element in a linked list.

We haven’t combined these two as it will be very easy for you to combine these two and to get the kth largest element in the linked list

There is another method you can try i.e. find the largest no. in an array and then exchange it with 0. Repeat the same upto k times to get the kth largest number.

Hope you understand the concept behind the code. If you have any feedback or query, feel free to comment.

You might like

Deepanshu

About the Author: Deepanshu

Machine Learning engineer at Clicklabs, Chandigarh

Leave a Reply

Your email address will not be published. Required fields are marked *

Close Bitnami banner
Bitnami