Sorting in Linked List
0% completed
Sorting in Linked List Notes
Quick Sort on Linked List
Count Inversion
Insertion Sort in Linked List
Sort Linked List
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

Given a Singly Linked List of integers, return its inversion count. The 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.

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.
Reset Code
Full screen
copy-code
Console