LeetCode Streak Challenge - Day 1/30 - Reverse list

I have decided to keep up a 30 day streak on LeetCode starting today. The idea is to be consistent, so I will start with 2 problems per day.

Problem 1: Reversing a list

Today's daily challenge question was about reversing lists. This topic has been discussed to death in many forums already. But I have found that trying to reproduce what I learnt/read, helps increase the retain the piece of information for longer in memory. Also I want to try and keep notes for each problem I solve so that I can revisit them later.

There are different ways to go about reversing a list in Python:

1. list.reverse() -
   • Reversing is done in place - It does not create a new object and reverse it. Instead it modifies the original copy.
   • The function does not return the modified list. We cannot assign the returned value of the function to a variable. The return value is None.
   • Another term for operating in place is side-effect.
   • Time complexity - O(n) where n is the number of elements in the list.
   • Space complexity - O(n).
2. reversed(list) -
   • It returns an iterator that allows traversing the list in reverse order.
   • We can call a list on the returned iterator to get the reversed list.
   • Any changes to the original list will impact the iterator because the iterator points to the same list and not a copy.
   • Time complexity - O(n) where n is the number of elements in the list.
   • Space complexity - O(n).
3. Swap the first element with the last, the second element with the second last, and so on.
   • Time complexity - O(n).
   • Space complexity - O(n).
4. Slicing
   • list[start:stop:step]. The default value of step is one, which allows the slicing to extract items from start to stop-1 from left to right. Setting the step to -1 returns the objects in reverse order.
   • It returns a reversed copy of the list.
   • Time complexity - O(n).
   • Space complexity - O(n).
5. Loops
   • We can loop through the list in reverse order and copy each element to a new list. Needless to say, this is not in place.
   • Time complexity - O(n).
   • Space complexity - O(n).

For methods 4 - 5, we can also use recursion. In this case, the Space complexity will include the Stack space which will be O(n). The maximum number of elements present in stack will be the size of the list, n.