Tag: python3

This post explains leetcode problem 206. reverse linked list using python 3. For example, let’s say there is a linked list: 1 -> 2-> 3-> 4 -> 5. After reversing the list, the expected result is 5 -> 4 -> 3 -> 2 -> 1. This is a fairly easy problem and there is a couple of ways to solve this.

Using stack

This method uses extra space (stack) as the name indicates. The algorithm is:
1. As iterating the original linked list, create the node and push it to the top of the stack. Note that the next pointer should be None
2. After #1, start popping the node from the stack. As you pop the node, connect it with previous (or next depending on your implementation)
3. After #2, you got the reversed linked list

Time complexity: O(n)
Space complexity: O(n) because you have to store all the nodes to the stack

This method is very simple and has pretty decent time complexity. However, even though time complexity is O(n), you are iterating each node twice: 1st when iterating the list, 2nd when popping from the stack. In addition to that, it also uses O(n) space complexity.

The question is, can we do better?

Optimized linked list reversal

We can actually reverse the list in a single traversal without using any extra space. Since code is quite simple, I will just show you the code first then explain.

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    reversed_list = None
    while head:
        next = head.next
        head.next = reversed_list
        reversed_list = head
        head = next
    return reversed_list

As you are iterating the original list, all you need to do is push the current node to the head of the new list. reversed_list is the head of the new list. While you are iterating the original list, save the next node because you are going to pop the current node from the original list and push to the head of the new list (line 4). At line 5,6 you are pushing the current node to the new list. Because you are setting the next pointer to the head of reversed_list, you are automatically disconnecting the node from the original list. At the line 6, it’s making sure to set the new head. Then you keep iterating by setting head to next node which was previously saved.

Time complexity is O(n) which is better than the method above because it only iterates the list one time. Space complexity is O(1) because it doesn’t require any extra space.