# Following is the class structure of the Node class:
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to convert the linked list into an array
def linked_list_to_array(head):
arr = []
current = head
while current is not None and current.data != -1:
arr.append(current.data)
current = current.next
return arr
# Merge function to count inversions
def merge_and_count(arr, temp_arr, left, mid, right):
i = left # Starting index for left subarray
j = mid + 1 # Starting index for right subarray
k = left # Starting index for sorted subarray
inv_count = 0
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp_arr[k] = arr[i]
i += 1
else:
# There are mid - i inversions because all elements in the left
# subarray (arr[i], arr[i+1], ..., arr[mid]) are greater than arr[j]
temp_arr[k] = arr[j]
inv_count += (mid - i + 1)
j += 1
k += 1
# Copy the remaining elements of left subarray, if any
while i <= mid:
temp_arr[k] = arr[i]
i += 1
k += 1
# Copy the remaining elements of right subarray, if any
while j <= right:
temp_arr[k] = arr[j]
j += 1
k += 1
# Copy the sorted subarray into the original array
for i in range(left, right + 1):
arr[i] = temp_arr[i]
return inv_count
# Function to implement merge sort and count inversions
def merge_sort_and_count(arr, temp_arr, left, right):
inv_count = 0
if left < right:
mid = (left + right) // 2
inv_count += merge_sort_and_count(arr, temp_arr, left, mid)
inv_count += merge_sort_and_count(arr, temp_arr, mid + 1, right)
inv_count += merge_and_count(arr, temp_arr, left, mid, right)
return inv_count
def calculateInversionCnt(head):
# Step 1: Convert the linked list to an array
arr = linked_list_to_array(head)
# Step 2: Create a temporary array for merge sort
n = len(arr)
temp_arr = [0] * n
# Step 3: Perform merge sort and count inversions
return merge_sort_and_count(arr, temp_arr, 0, n - 1)
# Helper function to create a linked list from a list of values
def create_linked_list(elements):
dummy = Node(0)
current = dummy
for elem in elements:
current.next = Node(elem)
current = current.next
return dummy.next
