206. Reverse Linked List

📝 Problem Details

• Title: 206. Reverse Linked List
• Link: https://leetcode.com/problems/reverse-linked-list/
• Difficulty: Easy
• Tags/Categories: Linked-List

💭What Were My Initial Thoughts?

- a naive solution would be to insert each element from the list into a vector or a stack (doesnt really matter what data structure)
- iterate through the datastructue in an order that would construct the list in the reverse order
- return the new list
- there is definetly a better way of solving this without the need for additional auxillary space 
- we can use a two pointers approach

🤔What Did I Struggle With?

~

💡 Explanation of Solution

- manage two pointers as we iterate through the list
	- prev (init to null)
	- curr : the current element in the list
	- tempNext: a temporary store of the next element from curr before we break the link between the two nodes 

⌛ Complexity Analysis

Time Complexity: O(n)
- we are iterating over n nodes in the list

Space Complexity: O(1)
- constatnt since there is no additional use of space in this problem

💻 Implementation of Solution

/**
 * 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) {
        if(head == nullptr || head->next == nullptr) return head;
 
        ListNode* curr = head;
        ListNode* prev = nullptr;
 
        while(curr != nullptr) {
            ListNode* tempNext = curr->next;
            curr->next = prev;
            prev = curr;
            curr = tempNext;
        }
 
        return prev;
    }
};