206_reverse_linked_list.cpp

/*
LeetCode 206 - Reverse Linked List
Difficulty: Easy

Problem:
Given the head of a singly linked list, reverse the list, and return the reversed list.

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

Example 2:
    Input: head = [1,2]
    Output: [2,1]

Example 3:
    Input: head = []
    Output: []

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

Time Complexity: O(n)
Space Complexity: O(1)
*/

#include <iostream>
#include <vector>

using namespace std;

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) {}
};

ListNode* makeList(vector<int> values) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int v : values) {
        cur->next = new ListNode(v);
        cur = cur->next;
    }
    return dummy.next;
}

vector<int> listToArray(ListNode* head) {
    vector<int> result;
    while (head) {
        result.push_back(head->val);
        head = head->next;
    }
    return result;
}

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next_node = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next_node;
        }
        return prev;
    }
};

int main() {
    Solution solution;

    ListNode* head1 = makeList({1, 2, 3, 4, 5});
    vector<int> result1 = listToArray(solution.reverseList(head1));
    cout << "[";
    for (int i = 0; i < result1.size(); i++) {
        cout << result1[i];
        if (i < result1.size() - 1) cout << ", ";
    }
    cout << "]" << endl; // [5, 4, 3, 2, 1]

    ListNode* head2 = makeList({1, 2});
    vector<int> result2 = listToArray(solution.reverseList(head2));
    cout << "[";
    for (int i = 0; i < result2.size(); i++) {
        cout << result2[i];
        if (i < result2.size() - 1) cout << ", ";
    }
    cout << "]" << endl; // [2, 1]

    vector<int> result3 = listToArray(solution.reverseList(nullptr));
    cout << "[]" << endl; // []

    return 0;
}