Problem 🤔

Reverse a linked list!

Example 1

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Real World Applications 🌎

The classic interview question!

The Finer Details 🔎

This question is deceptively simply. As I jokingly wrote above, this question is often used as an exemplary interview question. Because of this, let’s make sure we know it well :)

Naive Solution 💡

Complexity Analysis 🧮

Time complexity

O(n)

Loop over every node in list.

Space complexity

O(n)

Extra list of seen and new linked list of size n.

Recursive Solution 💡

Complexity Analysis 🧮

Time complexity

O(n)

Loop over every node in list.

Space complexity

O(n)

Depth of recursive call / stack

Optimal Iterative Solution 💡

Let’s be very careful with the pointers here! It helps to work this out with an example so let’s try the following:

Example

Input: 1->2->3

Output: 3->2->1

Complexity Analysis 🧮

Time complexity

O(n)

Loop over every node in list.

Space complexity

O(1)

Depth of recursive call / stack

Takeaways 🎉🥳

• When we review data structures I often emphasize that knowing how to implement CRUD operations is super useful and something we should strive to learn before moving on to more complicated questions. I would definitiley consdier reversing a linked list as a crucial operation!

Resources 📚 💻

• LeetCode