Untitled

// Singly-linked lists are already defined with this interface:
// template<typename T>
// struct ListNode {
//   ListNode(const T &v) : value(v), next(nullptr) {}
//   T value;
//   ListNode *next;
// };
//
// Function to reverse a linked list
ListNode<int>* reverse_linked_list(ListNode<int>* head) {
    ListNode<int>* prev = nullptr;
    ListNode<int>* curr = head;

    while (curr != nullptr) {
        ListNode<int>* tmp = curr;
        curr = curr->next;
        tmp->next = prev;
        prev = tmp;
    }
    return prev;  // New head of the reversed list
}

// Function to add two list elements with carry
std::pair<ListNode<int>*, int> add_list_elem(ListNode<int>* in1, ListNode<int>* in2, int carry) {
    int in1_val = (in1 != nullptr) ? in1->value : 0;
    int in2_val = (in2 != nullptr) ? in2->value : 0;
    int total = in1_val + in2_val + carry;

    return { new ListNode<int>(total % 10000), total / 10000 }; 
}

ListNode<int>* solution(ListNode<int>* a, ListNode<int>* b) {
    
    ListNode<int>* new_a = reverse_linked_list(a);
    ListNode<int>* new_b = reverse_linked_list(b);

    ListNode<int>* curr_a = new_a;
    ListNode<int>* curr_b = new_b;
    int carry = 0;
    ListNode<int>* new_head = nullptr;
    ListNode<int>* prev = nullptr;

    while (curr_a != nullptr || curr_b != nullptr) {
        auto [curr, new_carry] = add_list_elem(curr_a, curr_b, carry);
        carry = new_carry;

        if (prev) {
            prev->next = curr; 
        } else {
            new_head = curr; 
        }
        prev = curr;

        if (curr_a) curr_a = curr_a->next;  
        if (curr_b) curr_b = curr_b->next;  
    }

    if (carry) {
        ListNode<int>* carry_node = new ListNode<int>(carry);
        prev->next = carry_node;
    }

    new_head = reverse_linked_list(new_head);

    reverse_linked_list(new_a);
    reverse_linked_list(new_b);

    return new_head;  
}