0

Count Inversion

Difficulty: HARD
Avg. time to solve
50 min
Success Rate
30%

Problem Statement
Suggest Edit

Given a Singly Linked List of integers, return its inversion count. Inversion count of a linked list is a measure of how far it is from being sorted.

Two nodes n1 and n2 form an inversion if the value of n1 is greater than the value of n2 and n1 appears before n2 in the linked list.

Note :
You do not need to print anything, just return the inversion count for the given linked list. 
Input Format
The first and the only line of the input contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
Output Format:
A single integer denoting the inversion count of the given list.
Constraints:
0 <= L <= 10^5
-10^9 <= data <= 10^9 and data != -1

Where L is the number of nodes in the linked list.
Sample Input 1:
3 2 1 5 4 -1
Sample Output 1:
4
Explanation of the Sample Input 1:
For the given linked list, there are 4 inversions: (3, 2), (3, 1), (2, 1) and (5, 4). Thus, the inversion count is 4.
Sample Input 2:
0 6 8 7 -1
Sample Output 2:
1
Want to solve this problem? Login now to get access to solve the problems