Similar to question asked here (How to find the quartiles in the linked list with only one iteration).
I can easily find Quartile 1 using the method specified in the above post, however, quartile 3 is always wrong for me. Sometimes it is off by 1, and others 2 or more. I am moving the Quartile 3 pointer by 3 every iteration, is this correct, or am I missing something?
The idea is that the node references should make a step forward depending on the number of the iteration modulo 4:
The node reference for q1 should only move once in every 4 iterations, while the q2 node reference should step forward once every 2 iterations, and finally the q3 reference should step forward 3 out of 4 iterations.
Once the iterations are completed, it has to be decided whether the q* nodes are exactly on the corresponding median, or the average with its successor node should be taken. Again, this is determined by the size of the list modulo 4.
Here is a little implementation in JavaScript:
function makeList(arr) {
return arr.reduceRight((next, val) => ({ next, val }), null);
}
function* fromList(head) {
while (head) {
yield head.val;
head = head.next;
}
}
function getMedians(head) {
if (head == null || head.next == null) return; // Need at least 2 values
let node1 = head,
node2 = head,
node3 = head.next,
node4 = node3.next,
size = 2;
while (node4) {
if (size % 4 == 1) node1 = node1.next;
if (size % 2 == 0) node2 = node2.next;
if (size % 4 != 3) node3 = node3.next;
node4 = node4.next;
size++;
}
return [
size % 4 < 2 ? (node1.val + node1.next.val) / 2 : node1.val,
size % 2 < 1 ? (node2.val + node2.next.val) / 2 : node2.val,
size % 4 < 2 ? (node3.val + node3.next.val) / 2 : node3.val,
];
}
// Example run
let head = makeList([20, 30, 40, 50, 60, 70]);
console.log("list", ...fromList(head));
let [q1, q2, q3] = getMedians(head);
console.log("q1, q2, q3 => ", q1, q2, q3);