How to find the quartiles in the linked list with only one iteration

Question

I have a singly linked list of integers. The node is defined as

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

    };

I need to find the q1,q2, and q3( first, second and third quartile) respectively. It is easy to find using two-pass, as in first-pass find the length of the linked list and the second pass find the exact elements. But how to find it using only one pass traversal through the linked list? To find the q2(median) we can use the slow and fast pointer approach. ie in each iteration we will increment one pointer to one step and the second pointer to two-step. In that case, we will get the half-size position of the linked list.

But how to find the q1 and q3? I had done the code to find the median (q2)

void findQuartiles(Node *head)
{
    Node *q2 = head;
    Node *temp = head;
    int q2_data;
    while(temp)
    {
        q2_data = q2->value;
        q2 = q2->next;
        temp = temp->next->next;
    }
    cout<<"\nq2 = "<<q2_data;
}

This code was done in c++. It's ok if you can help me in other languages also.

Answer 1

I don't know what the best solution would be, but I would personally create a linked list wrapper that looks like the following (in C):

    //Individual node    
    struct linked_list_node {
        void * data;
        struct list_node next;
    };
    
    //List wrapper. Can contain more useful data about the list.
    struct linked_list {
        struct _private_node *head;
        struct _private_node *tail;
        int count;
    };

You don't need to include the tail in the wrapper, but it's useful to implement an append function with O(1) speed, and it doesn't take much memory. Adding a variable for counting the number of items is what would let you find the quartiles with one pass. Just with the count, you can already know what your median and quartile nodes will be, prepare variables for each, and then iterate through the list once to find the address of each specific node. If your data is numerical, you'll want to use doubles, because if you need to calculate the actual value of the medians and you have an even number, you'll have to calculate the average and have one chance out of two of ending up with a .5.