Python不使用额外数组空间 原地按空格分隔反转列表的实现方法

你的需求本质是原地反转列表中所有被空格分隔的连续非空格子段，不需要额外数组空间，仅用常数级临时变量就能实现，时间复杂度为O(n)，每个元素最多被访问两次。

实现思路 #

• 用指针记录当前待反转子段的左边界left，初始值为0
• 遍历整个列表，每次找到当前子段的右边界：即从left开始往后找第一个空格的前一位，就是当前子段的结束位置right
• 对[left, right]区间用双指针原地交换反转，仅需要1个临时变量存储交换值
• 把left更新为当前空格的下一位，重复上述步骤直到遍历完整个列表

完整可运行代码 #

# 原始列表
l = ['m','o','b','i','l','e', ' ','a','l','i', ' ']
n = len(l)
left = 0

while left < n:
    # 查找当前子段的右边界（第一个空格的前一位）
    right = left
    while right < n and l[right] != ' ':
        right += 1
    right -= 1
    
    # 双指针反转[left, right]区间
    cur_left, cur_right = left, right
    while cur_left < cur_right:
        # 原地交换，仅用1个临时变量
        temp = l[cur_left]
        l[cur_left] = l[cur_right]
        l[cur_right] = temp
        cur_left += 1
        cur_right -= 1
    
    # 跳转到下一个子段的起始位置
    left = right + 2

print(l)
# 输出：['e','l','i','b','o','m', ' ','i','l','a', ' ']

方案优势 #

• 完全符合要求：没有新增任何独立数组，仅用了left/right/cur_left/cur_right/temp5个临时变量，空间复杂度O(1)
• 时间复杂度最优：所有元素总共仅被遍历2次（一次查找边界、一次交换），时间复杂度O(n)
• 通用性强：不管列表里有多少个被空格分隔的子段都能正常处理，不需要提前知道子段数量

内容的提问来源于stack exchange，提问作者Hasan K.