单遍历链表求Quartile 3出错，每次移动3步是否正确？

你每次迭代把Q3指针固定移3步的思路完全错误，这是导致结果偏差的核心原因。问题出在你误解了四分位数的位置逻辑，忽略了链表长度的奇偶性、边界条件以及四分位数的定义规则。

核心错误分析 #

链表的四分位数定位本质是基于有序链表的位置比例：

• Q1对应数据的前25%位置，Q3对应前75%位置
• 不同统计规则下，位置计算略有差异，但核心是Q3的位置是总长度的3/4比例，而非步长直接乘3

固定步长移动Q3的方式，会在链表长度不是4的倍数时出现偏移：比如长度为5时，3/4位置是第4个元素（1-based），但固定移3步会直接跳到第4个节点？不对，若从表头开始每次移3步，第一次迭代就会跳到第4个节点，但如果遍历过程中每次移动主指针1步、Q3指针3步，会直接超出链表范围，或者在长度为6时，Q3的正确位置是第5个元素，固定步长会导致多移或少移。

正确实现思路 #

无论是否单迭代，核心都是先明确四分位数的位置规则，再根据总长度计算目标位置。

方案1：两次迭代（最可靠，易实现）

这是工业界常用的方式，容错率高：

1. 第一次遍历链表，统计总长度n
2. 根据规则计算Q1和Q3的目标位置：
   • 1-based索引：q1_pos = (n + 3) // 4（向上取整前25%），q3_pos = (3 * n + 3) // 4（向上取整前75%）
   • 0-based索引：q1_pos = (n - 1) // 4，q3_pos = (3 * n - 1) // 4
3. 第二次遍历链表，移动到对应位置的节点，即为Q1和Q3

方案2：单迭代实现（需动态判断）

若必须用一次遍历，需在遍历过程中同步计数并动态调整指针位置：

def find_quartiles(head):
    if not head:
        return (None, None)
    
    q1_ptr = head
    q3_ptr = head
    current = head
    count = 0
    
    while current:
        count += 1
        # 计算当前count对应的Q1和Q3应处的位置（1-based）
        target_q1 = (count + 3) // 4
        target_q3 = (3 * count + 3) // 4
        
        # 移动Q1指针到目标位置
        current_q1_pos = 0
        temp = head
        while temp != q1_ptr:
            current_q1_pos +=1
            temp = temp.next
        if current_q1_pos +1 < target_q1 and q1_ptr.next:
            q1_ptr = q1_ptr.next
        
        # 移动Q3指针到目标位置
        current_q3_pos =0
        temp = head
        while temp != q3_ptr:
            current_q3_pos +=1
            temp = temp.next
        if current_q3_pos +1 < target_q3 and q3_ptr.next:
            q3_ptr = q3_ptr.next
        
        current = current.next
    
    return (q1_ptr.val, q3_ptr.val)

不过这种方式因为每次都要计算当前指针位置，时间复杂度还是O(n)，但代码较繁琐。更简洁的单迭代方式是用比例计数：

def find_quartiles(head):
    q1 = head
    q3 = head
    current = head
    step = 0
    
    while current:
        step +=1
        # Q1每4步移动1次
        if step %4 == 1:
            q1 = q1.next if q1.next else q1
        # Q3每4步移动3次，通过判断step的模值实现
        if step %4 in (1,2,3):
            q3 = q3.next if q3.next else q3
        current = current.next
    
    # 最后根据总长度调整边界情况
    n = step
    if n %4 ==1:
        # 总长度为4k+1时，Q3需要回退1步
        temp = head
        for _ in range((3*n +3)//4 -2):
            temp = temp.next
        q3 = temp
    elif n%4 ==2:
        # 总长度为4k+2时，Q3需要回退1步
        temp = head
        for _ in range((3*n +3)//4 -2):
            temp = temp.next
        q3 = temp
    
    return (q1.val, q3.val)

这段代码通过模运算实现比例移动，最后针对非4倍数的长度做边界修正，能解决大部分偏差问题。

关键注意事项 #

1. 明确四分位数规则：不同统计场景下四分位数的计算规则不同，比如Tukey的hinges方法是将数据分两半后取各自中位数，这种情况下Q3的位置和常规比例计算不同，需先确认业务场景要求。
2. 索引定义一致性：全程保持0-based或1-based索引一致，不要混用，否则必然出现位置偏差。
3. 空链表/短链表处理：当链表长度小于4时，Q1和Q3可能与中位数重合，需单独处理边界情况。

内容的提问来源于stack exchange，提问作者Gottfried Leibniz