2. Linked a Linked List

Problem Statement

2. Linked a Linked List Problem Statement You are given an array of size n . You have to create a new linked list with exactly n/2 nodes. The value of each node in the new linked list is determined by taking the mean of pairs of elements from the original array. Specifically, the first node of the new linked list will have a value equal to the mean of the largest and smallest values in the given array. The second node will have the mean of the second largest and second smallest values, and so on. The mean of two integers a and b is calculated as (a + b) / 2 using floor division. Input Format First-line will contain an integer n , denoting the size of the array. The next n lines will contain an integer each. Constraints 1 < n ≤ 10 5 n will always be even . 1 ≤ array elements ≤ 10 6 Output Format Return the head of the newly created LinkedList. Example Input: n = 6 arr = [4, 1, 6, 5, 2, 4] Output: 3 -> 3 -> 4 Explanation: The given array is [4, 1, 6, 5, 2, 4]. 1. First, sort