Count Inversions - ll
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
Initially, we declare a counter ‘INVERSIONCNT’ and initialize it with ‘0’, Where ‘INVERSIONCNT’ maintains the count of inversions in the given linked list. Also, Declare a pointer ‘CUR’, initialized to the ‘HEAD’ of the linked list, to traverse the entire list, and also a pointer ‘TEMP’ to traverse the part of the linked list after ‘CUR’.
For every node pointed by the ‘CUR’, we use the ‘TEMP’ pointer to start traversal from the node next to the ‘CUR’. We compare the values of the nodes pointed by the pointer ‘TEMP’ and the ‘CUR’ pointer and if the value pointed by ‘CUR’ is greater than that pointed by ‘TEMP’, then the 2 nodes form an inversion pair and we increment the counter ‘INVERSIONCNT’ by ‘1’.
We repeat the entire process till ‘CUR’ reaches the end of the list.
This approach is based on the concept of merge sort and we count the number of inversions in the list during the merge step. We will have 2 sorted lists - ‘LEFT’ and ‘RIGHT’. We need to merge them and concurrently count the inversions. We will keep track of the current position in each list. Initially, this position is ‘0’ (the beginning of the list), and it can also point after the end of the list.
The steps are as follows:
- If both the current positions are inside their lists, then we have two cases:.
- The 'LEFT’ current element is less than or equal to the ‘RIGHT’ current element: We just copy the ‘LEFT’ current element into the resulting list and increment the ‘LEFT’ position.
- The ‘LEFT’ current element is greater than the ‘RIGHT’ current element: We copy the ‘RIGHT’ current element into the resulting list, increment the ‘RIGHT’ position and increment the inversions count by the number of remaining elements in the ‘LEFT’ list (including the 'LEFT' current element).
- Else if there are no ‘LEFT’ elements anymore, then we append the remaining ‘RIGHT’ list to the resulting list.
- Else we append the remaining ‘LEFT’ list to the resulting list.
