Share my c++ stack and reverse linked list solutions


  • 0
    B

    Using stack:

    class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            stack<int> s1, s2;
            ListNode *root=nullptr;
            int carry = 0;
            while(l1) {s1.push(l1->val); l1 = l1->next;}
            while(l2) {s2.push(l2->val); l2 = l2->next;}
            while(!s1.empty() || !s2.empty()) {
                int val1=0, val2 = 0;
                if(!s1.empty()) {
                    val1 = s1.top();
                    s1.pop();
                }
                if(!s2.empty()) {
                    val2 = s2.top();
                    s2.pop();
                }
                val1 += val2 + carry;
                carry = val1/10;
                ListNode* tmp = root;
                root = new ListNode(val1%10);
                root->next = tmp;
            }
            if(carry>0) {
                ListNode* tmp = root;
                root = new ListNode(carry);
                root->next = tmp;
            }
            return root;
        }
    };
    

    Reverse linked list (although not allowed, just write it as an exercise)

    class Solution {
    public:
        void reverseLinkedList(ListNode* &node) {
            if(!node) return;
            ListNode* prev = nullptr;
            while(node->next) {
                ListNode* tmp = node->next;
                node->next = prev;
                prev = node;
                node = tmp;
            }
            node->next = prev;
            return;
        }
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            int carry = 0;
            ListNode* root = nullptr;
            reverseLinkedList(l1);
            reverseLinkedList(l2);
            while(l1 || l2 || carry) {
                int val = ((l1)?l1->val:0) + ((l2)?l2->val:0) + carry;
                cout << val << endl;
                carry = val/10;
                ListNode* tmp = root;
                root = new ListNode(val%10);
                root->next = tmp;
                if(l1) l1 = l1->next;
                if(l2) l2 = l2->next;
            }
            return root;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.