Reverse Linked List - LeetCode Problem

Problem Description

Welcome back! Today, we'll be solving the Reverse Linked List problem on LeetCode.

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

For example, if the input linked list is 1 -> 2 -> 3 -> 4 -> 5 -> NULL, then the output linked list should be 5 -> 4 -> 3 -> 2 -> 1 -> NULL.

That's a fun problem to solve! Let's dive into the solution.

Solution

Our solution to this problem is straightforward. We'll start by initializing three pointers: prev, curr, and next. We'll set prev to NULL, curr to the head of the input linked list, and next to the next node after curr.

We'll then iterate through the linked list, changing the direction of each node's next pointer. Specifically, we'll set curr's next pointer to point to prev. We'll then update prev and curr to their next nodes. We'll continue doing this until curr reaches the end of the linked list.

Here's the Python code for our solution:

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head

        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next

        return prev

Let's go through this code step-by-step.

1. We start by initializing prev to NULL, curr to the head of the input linked list, and next to the next node after curr.

prev = None
curr = head

1. We then iterate through the linked list, changing the direction of each node's next pointer.

while curr:
    next = curr.next
    curr.next = prev
    prev = curr
    curr = next

Inside the loop, we set next to curr's next node. We then set curr's next pointer to point to prev. This reverses the direction of the next pointer for the current node. Finally, we update prev and curr to their next nodes.

1. We return prev, which is the new head of the reversed linked list.

return prev

That's it! The linked list is now reversed.

Complexity Analysis

Now that we have our solution, let's analyze its time and space complexity.

Time Complexity

Our solution iterates through each node in the linked list once. Since we're doing constant time operations for each node (updating pointers), the time complexity of our solution is O(n), where n is the length of the linked list.

Space Complexity

Our solution uses constant extra space. Therefore, the space complexity of our solution is O(1).

Conclusion

And there you have it! We've successfully tackled the Reverse Linked List problem. I hope you found this blog post helpful and informative. Happy Coding! 😎