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.