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.
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.