# LeetCode 206. Reverse Linked List

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?

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