Interquartile Range (IQR) in a Linked List: Slow and Fast Pointers

Quartiles are used in statistics to classify data. Per their name, they divide data into quarters. Given a set of data:

2, 4, 4, 5, 6, 7, 8 ^ ^ ^ Q₁ Q₂ Q₃ The lower quartile would be the value that separates the lowest quarter of the data from the rest of the data set. So in this instance, it would be the first 4. The middle quartile (also known as the median) separates the lowest 2 quarters of the data from the rest of the data set. The upper quartile separates the lowest 3 quarters of the data from the rest of the data set. The interquartile range is the difference between the third quartile and the first quartile: Q₃ - Q_1.

In case the number of values in the list is odd, the central element is a unique element. For example, if the list has a size = 9. The fifth element in the list will be the median. In case the number of values in the list is even, the central element is an average of two elements. For example, if the list has a size = 10. The average of the fourth and fifth element in the list will be the median. Q₁ is the median of the beginning and the element preceding median, and Q₃ is the median of the element succeeding median and the end.

Another example,

1, 2, 3, 4 ^ ^ ^ Q₁Q₂Q₃

Here, Q₂ = Average of 2 and 3 = 2.5

Q₁ = List consists of elements: 1, 2 (everything before median) = Average of 1 and 2 = 1.5

Q₃ = List consists of elements: 3, 4 (everything after median) = Average of 3 and 4 = 3.5

IQR = 3.5 - 1.5 = 2.0

Problem Statement

Weve given you sorted data in the form of a linked list (e.g, the above data would be inputted as 2->4->4->5->6->7->8). Given a singly linked list of integers that represents a data set (with head node head), return the interquartile range of the data set using the slow and fast pointer approach OR using a methodology that does not iterate over the linked list twice (for example: finding the count of number of elements in first iteration). You cannot use arrays, vectors, lists or an STL implementation of List ADT.

Node class defined:

class Node { public: int value; Node* next = NULL; };

Constraints

• The list is limited to positive numbers
• The list will have at least 4 values
• The list will not be empty
• The list is sorted

USE THIS TEMPLATE:

float interQuartile(Node* head) { //your code here

}