Reversing a Linked List - Leetcode Problem

If you want to try to solve this question first, here is the link

---

Table of Contents:

• The Question
• The Solution Code
• The Solution Explained
• Time and Space Complexity
• Conclusion

---

The Question

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

The Solution Code

# class Node:
#    def __init__(self, val=0, next=None):
#        self.val = val
#        self.next = next

def reverse(head):
    current = head
    previous = None

    while current:
        temp = current.next
        current.next = previous
        previous = current
        current = temp

    return previous

The Solution Explained

I think the best way to explain this solution is to take you through a single iteration and see how each line of code affects the linked list.

let's determine your starting point but initializing the current and previous variables. The current variable will be moving one spot forward each iteration, and the previous will be one node behind the current at each iteration.

The first step that you need to take in the while loop is to create a temporary variable to point to the next node after current.

If you don't do this then once we point current backwards, there would be nothing referencing the node and it will get garbage collected.

Now that you have a reference to the second node, it is safe to reverse the first node and point it back to your previous variable.

Now that you have reversed the first node, you have to move both the previous and the current nodes forward. It may seem strange that both temp and current are pointing at the same node, but remember the first step in the while loop will be to move temp forward.

Congratulations! You have made it through one iteration of reversing a linked list. This exact same process will happen again and again until the current variable is pointing to the None value at the end and the previous variable pointing at the 5.

After this has happened the previous node has become your new head node and you can return it and have a reversed linked list!

Time and Space Complexity

The space complexity is very simple for this question since you are not allocating any extra space proportional to the size of the linked list, you will get a space complexity of O(1).

The time complexity however does increase as the size of your linked list increases, however, you only have a single while loop, which goes over every element once so that will make the algorithm O(n) time.

---

Conclusion

Congrats! You should be proud of yourself, you can officially say that you know how to reverse a linked list 🎉.

Thank you for reading this article! I hope this solution has helped you work through this problem and helped develop your understanding of data structures and algorithms.

Have an amazing day!