LeetCode Python Solutions: 206. Reverse Linked List #python #coding #leetcode

Time & Space Complexity Balanced Solution || Fully Explained || Video

The approach of this solution is to reverse the linked list iteratively using three pointers: prev, curr, and next_node.

Here's a step-by-step breakdown of the approach:

1. Initialize two pointers, prev and curr, to None and head, respectively. These pointers are used to keep track of the previous and current nodes during the reversal process.

2. Enter a while loop that continues until curr becomes None, indicating the end of the original linked list.

3. Inside the loop: a. Store the reference to the next node in next_node before modifying the next pointer of curr. This step ensures that we don't lose the reference to the remaining part of the original list. b. Update the next pointer of curr to point to the previous node (prev). This step effectively reverses the direction of the pointer. c. Move both prev and curr one step forward. Set prev to the current node (curr) and curr to the next node (next_node).

4. Repeat steps 3a-3c until all nodes in the original list are visited and reversed.

5. Finally, when the loop ends, prev will be pointing to the new head of the reversed list. Return prev as the result.

By reversing the pointers in this iterative manner, the original linked list is reversed, and the reversed list is formed. This approach modifies the list in-place, meaning it doesn't create a new list or nodes.

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. The while loop iterates through each node in the linked list once, performing constant-time operations. Therefore, the time complexity is linearly proportional to the number of nodes.

The space complexity of this solution is O(1). It uses a constant amount of extra space to store the prev, curr, and next_node pointers. The space required does not depend on the size of the input linked list, so it remains constant regardless of the input size. Hence, the space complexity is constant.

The intuition behind this solution is to reverse the pointers of the linked list iteratively.

1. We initialize two pointers, prev and curr, where prev is initially set to None and curr points to the head of the linked list.
2. Inside the while loop, we have three steps: a. We store the reference to the next node in next_node before we modify the next pointer of curr. b. We update the next pointer of curr to point to the previous node (prev), effectively reversing the direction of the pointer. c. We move both prev and curr one step forward by updating their values to curr and next_node, respectively.
3. We continue this process until we reach the end of the linked list (curr becomes None).
4. Finally, we return prev, which will be pointing to the new head of the reversed list.
00:00 Code
01:57 Main
08:00 End

[NeedCodeLeetCode]

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next

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

prev = None # there is no previous node
curr = head # the head of the linked list, representing the current node we are working with

while curr:# iteration stops when curr becomes None(reach the end of the original list)
next_node = curr.next # store the reference to the next node so we don't lose the reference to the remaining part of the original list
curr.next = prev # update the next pointer of the current node to point to the previous node

# prepares us for the next iteration of the loop, where we reverse the pointer of the next node.
prev = curr # move prev one step forward
curr = next_node # move curr one step forward


1. First, we define a class ListNode. This class represents a node in a linked list. Each node has a value (val) and a reference to the next node (next).
2. The __init__ method is a special method in Python that gets called when a new object of the ListNode class is created. It initializes the attributes of the object. In this case, it takes two optional parameters: val (defaulted to 0) and next (defaulted to None). It assigns the provided values to the respective attributes of the object.
3. Next, we define a function reverseList that takes head as a parameter. The head parameter represents the first node of the linked list.
4. Inside the function, we initialize two variables: prev and curr. prev is set to None, indicating that there is no previous node initially. curr is assigned the value of the head node, representing the current node we are working with.
5. We enter a while loop that continues until curr becomes None. This loop iterates through the linked list, one node at a time.
6. Inside the loop, we perform the following operations: a. We store the reference to the next node in the variable next_node. This is done to ensure we don't lose the reference to the remaining part of the original list. b. We update the next pointer of the current node (curr.next) to point to the previous node (prev). This step effectively reverses the direction of the pointer. c. We move both prev and curr one step forward. We set prev to the current node (curr) and curr to the next node (next_node).
7. The loop continues until all nodes in the original list are visited and reversed.
8. When the loop ends, prev will be pointing to the new head of the reversed list. This is because, during the reversal process, the prev pointer keeps track of the previously visited nodes, effectively becoming the new head of the reversed list.
9. Finally, we return prev as the result, which represents the head of the reversed list.