Reverse Linked List - LeetCode Problem

Search for a command to run...

No comments yet. Be the first to comment.
Problem Description Welcome to another fun coding challenge! Today, we'll be tackling the Guess Number Higher or Lower problem. You are playing the Guess Game with your friend. In this game, your friend thinks of a number between 1 and n, and you hav...

Problem Description Welcome to another fun coding challenge! Today, we'll be tackling the Search in Rotated Sorted Array problem. Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [...

Problem Description Welcome to another fun coding challenge! Today, we'll be tackling the Find Minimum in Rotated Sorted Array problem. Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nu...

Problem Description Welcome to another fun coding challenge! Today, we'll be tackling the Min Stack problem. Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop...

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.
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.
prev to NULL, curr to the head of the input linked list, and next to the next node after curr.prev = None
curr = head
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.
prev, which is the new head of the reversed linked list.return prev
That's it! The linked list is now reversed.
Now that we have our solution, let's analyze its time and space 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.
Our solution uses constant extra space. Therefore, the space complexity of our solution is O(1).
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! 😎