 0

# Count Inversion

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

Problem Statement
Suggest Edit

#### 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
`````` 