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

Time & Space Complexity Balanced Solution || Fully Explained || Video
https://leetcode.com/problems/reverse-linked-list/solutions/3750651/time-space-complexity-balanced-solution-fully-explained-video/

Twitter: https://twitter.com/QiaoLiuCiao

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