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

Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

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.

Input:

A singly linked list represented by its head node.

Output:

The head of the reversed linked list.

Constraints:

• The number of nodes in the list is in the range [0, 5000].
• -5000 <= Node.val <= 5000

Example:

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 nodes in a singly linked list. This problem is significant in many applications, such as reversing data streams or undoing operations. A common pitfall is losing access to the next node when reversing the link, which can be avoided by careful pointer manipulation.

Approach

To solve this problem, we need to reverse the direction of the links between nodes. We can achieve this by iterating through the list and adjusting the pointers.

Naive Solution

A naive approach might involve using additional space to store the nodes in a different order, but this would not meet the O(1) space requirement.

Optimized Solution

We can use an iterative approach with three pointers: prev, current, and next. This method ensures we reverse the list in O(n) time and O(1) space.

Steps:

1. Initialize three pointers: prev to null, current to head, and next to null.
2. Iterate through the list, reversing the links by adjusting the next pointer of the current node to point to prev.
3. Move the prev and current pointers one step forward.
4. Continue until all nodes are processed.
5. Return prev as the new head of the reversed list.

Algorithm

Here is a step-by-step breakdown of the algorithm:

1. Initialize prev to null and current to head.
2. While current is not null:
   • Store current->next in next.
   • Set current->next to prev.
   • Move prev to current.
   • Move current to next.
3. Return prev as the new head.

Code Implementation

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr; // Initialize previous node to null
        ListNode* current = head; // Start with the head node
        ListNode* next = nullptr; // Initialize next node to null
        
        while (current != nullptr) { // Traverse the list
            next = current->next; // Store the next node
            current->next = prev; // Reverse the current node's pointer
            prev = current; // Move prev to current node
            current = next; // Move to the next node
        }
        
        return prev; // prev will be the new head of the reversed list
    }
};

Complexity Analysis

The time complexity of this approach is O(n) because we traverse the list once. The space complexity is O(1) as we only use a constant amount of extra space for the pointers.

Edge Cases

Consider the following edge cases:

• An empty list (head is null): The function should return null.
• A list with one node: The function should return the same node.

Testing

To test the solution comprehensively, consider the following test cases:

1. Input: head = []
   Output: []

2. Input: head = [1]
   Output: [1]

3. Input: head = [1, 2, 3, 4, 5]
   Output: [5, 4, 3, 2, 1]

4. Input: head = [1, 2]
   Output: [2, 1]

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Understand the structure of the data (linked list in this case).
• Visualize the problem with diagrams.
• Break down the problem into smaller steps.
• Consider edge cases and test your solution thoroughly.

Conclusion

Reversing a linked list is a fundamental problem that helps in understanding pointer manipulation and linked list operations. Mastering this problem enhances your problem-solving skills and prepares you for more complex data structure challenges.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode: Reverse Linked List
• GeeksforGeeks: Reverse a Linked List
• Coursera: Data Structures