Reverse Linked List in O(n) Time and O(1) Space using Python

Note:

Your algorithm should run in O(n) time and use O(1) extra space.

## Problem Definition The task is to reverse a singly linked list. Given the head of the list, we need to reverse the list and return the new head of the reversed list. ### Input: - `head`: The head node of a singly linked list. ### Output: - The head node of the reversed singly linked list. ### Constraints: - The number of nodes in the list is in the range `[0, 5000]`. - `-5000 <= Node.val <= 5000` ### Example: plaintext Input: head = [1, 2, 3, 4, 5] Output: [5, 4, 3, 2, 1] ## Understanding the Problem The core challenge is to reverse the links between the nodes of the linked list. This problem is significant in many applications, such as reversing data structures, undo operations, and more. A common pitfall is losing track of the next node when reversing the links. ## Approach ### Naive Solution A naive approach might involve using additional space to store the nodes in a list and then reconstructing the linked list in reverse order. However, this would not meet the space complexity requirement of O(1). ### Optimized Solution We can reverse the linked list in-place using an iterative approach with three pointers: 1. `prev`: Points to the previous node. 2. `current`: Points to the current node. 3. `next_node`: Points to the next node. By iterating through the list and reversing the links, we can achieve the desired result in O(n) time and O(1) space. ### Detailed Steps: 1. Initialize `prev` to `None` and `current` to `head`. 2. Iterate through the list: - Store the next node (`next_node = current.next`). - Reverse the link (`current.next = prev`). - Move `prev` and `current` one step forward (`prev = current`, `current = next_node`). 3. After the loop, `prev` will be the new head of the reversed list. ## Algorithm ### Step-by-Step Breakdown 1. **Initialization**: - `prev` is set to `None`. - `current` is set to `head`. 2. **Iteration**: - While `current` is not `None`: - Save the next node (`next_node = current.next`). - Reverse the current node's pointer (`current.next = prev`). - Move `prev` and `current` one step forward (`prev = current`, `current = next_node`). 3. **Return**: - Return `prev` as the new head of the reversed list. ## Code Implementation

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

def reverseList(head: ListNode) -> ListNode:
    # Initialize previous node to None
    prev = None
    # Initialize current node to head
    current = head
    
    # Iterate through the list
    while current:
        # Save the next node
        next_node = current.next
        # Reverse the current node's pointer
        current.next = prev
        # Move prev and current one step forward
        prev = current
        current = next_node
    
    # Return the new head of the reversed list
    return prev

## Complexity Analysis ### Time Complexity - The algorithm runs in O(n) time, where n is the number of nodes in the linked list. This is because we iterate through the list once. ### Space Complexity - The algorithm uses O(1) extra space, as we only use a few pointers for the reversal process. ## Edge Cases ### Empty List - If the input list is empty (`head` is `None`), the function should return `None`. ### Single Node List - If the list contains only one node, the function should return the same node as the head of the reversed list. ### Testing To test the solution comprehensively, consider the following test cases: 1. An empty list. 2. A list with a single node. 3. A list with multiple nodes. 4. A list with negative values. 5. A list with duplicate values. ### Example Test Cases python # Helper function to create a linked list from a list def create_linked_list(arr): if not arr: return None head = ListNode(arr[0]) current = head for val in arr[1:]: current.next = ListNode(val) current = current.next return head # Helper function to convert a linked list to a list def linked_list_to_list(head): result = [] current = head while current: result.append(current.val) current = current.next return result # Test cases head = create_linked_list([1, 2, 3, 4, 5]) reversed_head = reverseList(head) print(linked_list_to_list(reversed_head)) # Output: [5, 4, 3, 2, 1] head = create_linked_list([]) reversed_head = reverseList(head) print(linked_list_to_list(reversed_head)) # Output: [] head = create_linked_list([1]) reversed_head = reverseList(head) print(linked_list_to_list(reversed_head)) # Output: [1] ## Thinking and Problem-Solving Tips 1. **Understand the Problem**: Break down the problem into smaller parts and understand the requirements. 2. **Visualize**: Draw diagrams to visualize the linked list and the reversal process. 3. **Iterate and Improve**: Start with a simple solution and iteratively improve it. 4. **Practice**: Solve similar problems to strengthen your understanding and skills. ## Conclusion Reversing a linked list is a fundamental problem that helps in understanding linked list manipulations. By using an iterative approach with three pointers, we can achieve an efficient solution with O(n) time complexity and O(1) space complexity. Practice and understanding of such problems are crucial for mastering data structures and algorithms. ## Additional Resources - [LeetCode - Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/) - [GeeksforGeeks - Reverse a Linked List](https://www.geeksforgeeks.org/reverse-a-linked-list/) - [Python Documentation - Data Structures](https://docs.python.org/3/tutorial/datastructures.html) Happy coding!