LeetCode 092 Reverse Linked List II：为何我的第二份提交比第一份慢

以下是两份Reverse Linked List II的代码：

实现1 #

// #1
ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (left >= right)
        return head;

    // always the precedence node next pointer addr
    // when left == 1, it goes to the head variable addr
    ListNode** left_pred_next_addr = &head;
    for (int i = 1; i < left; ++i)
        left_pred_next_addr = &(*left_pred_next_addr)->next;

    ListNode* p = *left_pred_next_addr;
    ListNode* q = p->next;
    ListNode* t;

    ListNode* right_node_next = p;
    for (int i = left; i <= right; ++i)
        right_node_next = right_node_next->next;

    for (;;)
    {
        t = q->next;
        q->next = p;
        if (t == right_node_next)
            break;
        p = q;
        q = t;
    }
    (*left_pred_next_addr)->next = right_node_next;
    *left_pred_next_addr = q;
    return head;
}

运行结果：

实现2 #

// #2
ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (left >= right)
        return head;

    ListNode** left_pred_next_addr = &head;
    for (int i = 1; i < left; ++i)
        left_pred_next_addr = &(*left_pred_next_addr)->next;

    ListNode* p = *left_pred_next_addr;
    ListNode* q = p->next;
    ListNode* t = nullptr;

    ListNode* right_node_next = p;
    for (int i = left; i < right; ++i)
    {
        t = q->next;
        q->next = p;
        p = q;
        q = t;
    }
    (*left_pred_next_addr)->next = t;
    // (*left_pred_next_addr)->next = right_node_next;
    *left_pred_next_addr = p;
    return head;
}

运行结果：

疑问 #

第二份代码省去了一次[left, right]区间的遍历，理论上运行速度应该比第一份提交更快，但LeetCode返回的运行结果反而更慢。两种方法各测试了两次，输出结果均一致。请问LeetCode运行测试用例时是否使用未开启优化的调试代码进行编译？ #

解答 #

• LeetCode的C++提交默认开启O2优化，并非以调试模式编译，你观察到的耗时差异和编译优化等级无关。
• 0ms和4ms的差异不具备统计意义，LeetCode的运行耗时统计本身存在较大误差：服务器负载波动、测试用例调度差异、进程上下文切换开销都会带来几ms的偏差，你可以尝试多提交几次两份代码，大概率都能跑出0ms到4ms不等的结果。
• 你提到的第二份代码省掉一次遍历的优化逻辑是成立的，但该额外遍历只有读操作，现代CPU缓存命中率极高的场景下，这点开销本身就极小，和测速误差比起来完全可以忽略。
• 如果要准确对比两份代码的性能差异，需要自行构造大压力测试用例（比如长度10万以上的链表），重复运行上万次后取平均耗时才能得到稳定的对比结果，LeetCode的耗时仅做参考，不能作为精确的性能基准。

内容的提问来源于stack exchange，提问作者Steven Liang