Make Maximum Number
Given a linked list such that each node represents a digit. Construct the maximum number possible from the given digits.

You just need to print the maximum Integer that can be formed

Input format :

The first and only line of each test case consists of Linked list elements of length n (separated by space and terminated by -1)

Output format :

The maximum Number that is formed using the digits present in the linked list.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Make Maximum Number

Given a linked list such that each node represents a digit. Construct the maximum number possible from the given digits.

You just need to print the maximum Integer that can be formed

Input format :

The first and only line of each test case consists of Linked list elements of length n (separated by space and terminated by -1)

Output format :

The maximum Number that is formed using the digits present in the linked list.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= N  <= 10^6
0 <= data <= 9

Time Limit: 1sec

Follow Up:

Can you do this in O(N) time and constant space?

Accepted Answer

Approach :

1) Traverse the linked list from start to end and make frequency array of all digits (0-9) present in the linked list.

2) Make the string starting from the maximum of digits (0-9) present in the linked list i.e first append all the 9’s in the answer string then append all the 8’s at the end of the answer string so on for all the other digits in the decreasing order.

3) Finally, return the formed answer string.

TC : O(N), where N = length of the Linked List
SC : O(1)

Accepted Answer

Sorting

Traverse in the linked list and store the elements in the vector or array, then sort the array or vector and then reverse the array or vector, return the number as string formed using the digits formed in the same order as in array or vector.

Space Complexity: O(1)Explanation:

O(N), where N is the length of Linked List

The extra space is used to create a vector of the same size as the length of the linked list.

Time Complexity: O(1)Explanation:

O(N log(N)), where N is the length of Linked List

Since sorting is used to form the largest number from digits.

Accepted Answer

Making Frequency Array

Traverse the linked list from start to end and make frequency array of all digits (0-9) present in the linked list and make the string starting from the maximum of digits (0-9) present in the linked list I.e first append all the 9’s in the answer string then append all the 8’s at the end of the answer string so on for all the other digits in the decreasing order.

Finally, return the formed answer string.

Space Complexity: O(1)Explanation:

O(1)

Constant space is used to create a fixed-size array of size 10 as a frequency array.

Time Complexity: O(n)Explanation:

O(N), where N is the length of Linked List

Since we only need to traverse in the linked list once.