如何降低while循环时间复杂度 优化Python列表排列代码

当前代码时间复杂度为O(n²)，大输入下无法通过耗时测试，核心低效点：

• list.pop(0) 是线性时间操作：弹出首元素需要移动后续所有元素，单次耗时O(n)
• 循环内反复调用list.reverse()，每次需要遍历全部剩余元素，单次耗时O(k)（k为当前剩余列表长度）
• 初始对输入列表做全拷贝也会带来额外的内存和时间开销

不需要实际执行弹出元素、反转剩余列表的操作，用双指针标记当前剩余元素的区间边界，配合一个布尔标记记录当前取数方向是否对应反转状态，即可单次遍历完成结果构造，全程不修改原输入列表，时间复杂度降到O(n)。

逻辑对应规则：

1. 初始左指针指向列表头（索引0），右指针指向列表尾（索引len(s)-1），反转标记初始为False
2. 每轮如果左右指针相遇，说明只剩1个元素，直接加入结果后结束
3. 反转标记为False时，按原顺序取左指针、右指针对应元素加入结果，之后左指针右移一位、右指针左移一位
4. 反转标记为True时，对应剩余序列已经反转的状态，取右指针、左指针对应元素加入结果，之后右指针左移一位、左指针右移一位
5. 每轮结束后翻转反转标记，进入下一轮

def arrange(s):
    n = len(s)
    T = []
    if n == 0:
        return T
    left, right = 0, n - 1
    reverse_toggle = False
    while left <= right:
        if left == right:
            T.append(s[left])
            break
        if not reverse_toggle:
            T.append(s[left])
            T.append(s[right])
            left += 1
            right -= 1
        else:
            T.append(s[right])
            T.append(s[left])
            right -= 1
            left += 1
        reverse_toggle = not reverse_toggle
    return T

以示例输入[1,2,3,4,5,6]测试：

• 第一轮：标记为False，取1、6，指针移动到left=1、right=4，标记翻转为True
• 第二轮：标记为True，取5、2，指针移动到left=2、right=3，标记翻转为False
• 第三轮：标记为False，取3、4，指针移动到left=3、right=2，循环结束
• 最终输出[1,6,5,2,3,4]，完全匹配预期结果。

该实现没有任何线性复杂度的嵌套操作，即使输入列表长度到十万、百万级也能快速跑完。

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