Этот код должен перевернуть список, но поменять местами только первый и последний элементы

Question

class Solution:
    def reverseString(self, s: List[str]) -> None:
        if(len(s)<=1):
            return
        s[0],s[-1] = s[-1],s[0]
        self.reverseString(s[1:-1])

это был вопрос по LeetCode. Мы должны перевернуть список с помощью рекурсии без использования дополнительной памяти, т.е. на месте.

Я написал этот код, но я не уверен, почему он не работает. Например, когда s = ['h', 'e', 'l', 'l', 'o'], вывод будет ['o', 'e', 'l', 'l', 'h'] вместо ['o', 'l', 'l', 'e', 'h'] - он поменяет местами только первый и последний элементы списка.

Answer 1

Для меня работает следующее:

def reverse_inplace(char_list, step=1):
    start, stop = step - 1, -step
    if step == 1:
        pass
    elif len(char_list[start:stop]) <= 1:
        return
    char_list[start], char_list[stop] = char_list[stop], char_list[start]
    reverse_inplace(char_list, step=step+1)

Это передает одну и ту же ссылку списка каждому рекурсивному вызову и просто отслеживает, как далеко вы находитесь в процессе с параметром step.

reverse_inplace(list("hello")) выходы:

['o', 'l', 'l', 'e', 'h']

Answer 2

Вид исправления для вашей концепции:

def reverseString(s, n=0):
    if(n==len(s)//2):
        return
    else:
        s[n], s[-n-1]=s[-n-1], s[n]
        reverseString(s, n+1)

x=list("new york")
reverseString(x)
print(''.join(x))
#outputs: kroy wen
x=list("hello")
reverseString(x)
print(''.join(x))
#outputs: olleh