Leetcode 2 Solution

This article provides solution to leetcode question 2 (add-two-numbers).
Categories:
Tags:
Access this page by simply typing in "lcs 2" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/add-two-numbers

Thinking Process

This is a basic question. The solution to the question is basically to simulate the calculation process, i.e., adding each digits while doing the iteration. Be sure to keep the carry bit.

Time & Space Complexity

Assuming N is the size of the bigger list, the time & space compelxities are:

  • Time complexity: O(N)
  • Space complexity: O(N)

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* res = NULL;
        ListNode* cur = NULL;

        bool carry = false;

        while (l1 || l2)
        {
            int val = 0;

            if (l1)
            {
                val += l1->val;
                l1 = l1->next;
            }

            if (l2)
            {
                val += l2->val;
                l2 = l2->next;
            }

            if (carry)
            {
                val++;
                carry = false;
            }

            if (val >= 10)
            {
                val -= 10;
                carry = true;
            }

            ListNode* node = new ListNode(val);

            if (res == NULL)
            {
                res = node;
                cur = node;
            }
            else
            {
                cur->next = node;
                cur = node;
            }
        }

        if (carry)
            cur->next = new ListNode(1);

        return res;
    }
};