# Cracking the Coding Interview - Reverse a Null Terminated String

1.1 Implement a function void reverse(char str) in C or C++ which reverses a null-terminated string*

Instead of using C, I’m going to simulate a null terminated string in python with a `None` terminated list of characters.

## Iterative with O(N) space

``````def reverse_none_terminated_list(char_list):
reversed_list = []
last_idx = len(char_list) - 2 # skip the None character
for i in range(last_idx, -1, -1):
reversed_list.append(char_list[i])
reversed_list.append(None) # put back the None character
return reversed_list
``````

## Iterative in-place

``````def reverse_none_terminated_list(char_list):
mid = (len(char_list) - 1) // 2 # again, ignore the None character
last_idx = len(char_list) - 2
for left_idx in range(mid):
right_idx = last_idx - left_idx
char_list[left_idx], char_list[right_idx] = char_list[right_idx], char_list[left_idx]
return char_list
``````

Note that I’m not using a temporary variable to perform the swap above. This is possible because, unlike other expressios, python assignment expressions are evaluated from right to left.

## Recursive in-place

Gayle mentions the possibility of a recursive approach in the book, so I took a stab at it:

``````def reverse_none_terminated_list((char_list):
mid = (len(char_list) - 1) // 2
last_idx = len(char_list) - 2
def reverse(left_idx):
if left_idx == mid:
return
reverse(left_idx + 1)
temp = char_list[left_idx]
right_idx = last_idx - left_idx
char_list[left_idx], char_list[right_idx] = char_list[right_idx], char_list[left_idx]
reverse(0)
return char_list
``````

This uses the same approach as the iterative in-place, I just swapped the loop-based iteration for recursion based on the same terminating condition based on the `mid` value. Unlike the iterative in-place approach, this swaps values from right to left on the left half of the list.