This code should reverse the list but only swaps first and last elements

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])

this was a question on LeetCode. We have to reverse the list using recursion without using extra memory, i.e in-place.

I wrote this code but I am not sure why it is not working. For example, when s = ['h', 'e', 'l', 'l', 'o'], the output is ['o', 'e', 'l', 'l', 'h'] instead of ['o', 'l', 'l', 'e', 'h'] - it only swaps the first and last elements of the list.

Strings in Python are immutable. You can't reverse one without using more memory. Also, why are you building a class for this? Python isn't Java. :) — PMende, Jan 23 '20 at 19:22
Try using [this](https://stackoverflow.com/a/931095/12282360) method. — Noah, Jan 23 '20 at 19:22
That is because `s[1:-1]` creates a copy of the list so the next recursive call doesn't actually change the original list — Tomerikoo, Jan 23 '20 at 19:27
Tomerikoo, how can I change the original list then using this approach — Ankur Gupta, Jan 23 '20 at 19:29
@PMende It's likely in a class because that's the boilerplate code for an online competitive programming site like LeetCode. — kaya3, Jan 23 '20 at 19:31

score 1 · Answer 1 · answered Jan 23 '20 at 19:55

The following works for me:

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)

This passes the same list reference to each recursive call, and simply keeps track of how far along you are in the process with a step parameter.

reverse_inplace(list("hello")) outputs:

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

Grzegorz Skibinski · Answer 2 · 2020-01-23T22:00:40.660

0

Kind of a fix for your concept:

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

edited Jan 23 '20 at 22:00

answered Jan 23 '20 at 21:06

Grzegorz Skibinski

12,624
2
11
34

This code should reverse the list but only swaps first and last elements

2 Answers2