0% completed
Count Inversion
Sort Linked List of 0's ,1's and 2's 15

# Count Inversions - ll

Difficulty: MEDIUM Contributed By
Deep Mavani
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.

##### 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 not be a list element.
``````
##### Output Format:
``````Print a single integer denoting the inversion count of the given linked list.
``````
##### Note:
``````You don't need to print the output, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````0 <= L <= 10^5
-10^9 <= data <= 10^9 and data != -1

Where L is the number of nodes in the linked list and 'data' is the node value of the linked list.

Time Limit: 1 sec
``````
##### 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 of the given linked list is 4.
``````
##### Sample Input 2:
``````0 6 8 7 -1
``````
##### Sample Output 2:
``````1
``````
##### Explanation of the Sample Output 2:
``````For the given linked list, there is only 1 inversion: (8, 7). Thus, the inversion count of the given linked list is 1.
``````   Console