Add Two Numbers - Leetcode Solution

Problem Statement:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.

Solution:

One way to solve this problem is to traverse the two linked lists simultaneously, adding the corresponding nodes and maintaining a carry variable. We create a new linked list whose nodes contain the digits of the sum. We start with the least significant digits and progress towards the most significant digits.

Algorithm:

1. Initialize a pointer curr to head of a new linked list
2. Initialize variables carry, sum to 0
3. Traverse the two linked lists simultaneously until either of them becomes null
4. Add the values of the current nodes and the carry variable
5. Calculate the sum and the carry by dividing the sum by 10
6. Create a new node with the value of the least significant digit of the sum
7. Set the next pointer of the current node to the new node
8. Move the pointers of both the linked lists to the next nodes
9. When the iteration ends, if the carry is non-zero, create a new node with the carry as its value and set its next pointer to null
10. Return the head of the new linked list

Code:

/**
 * 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* head = new ListNode(0);
        ListNode* curr = head;
        int carry = 0;
        int sum = 0;
        while (l1 != NULL || l2 != NULL) {
            int x = (l1 != NULL) ? l1->val : 0;
            int y = (l2 != NULL) ? l2->val : 0;
            sum = x + y + carry;
            carry = sum / 10;
            curr->next = new ListNode(sum % 10);
            curr = curr->next;
            if (l1 != NULL) l1 = l1->next;
            if (l2 != NULL) l2 = l2->next;
        }
        if (carry > 0) {
            curr->next = new ListNode(carry);
        }
        return head->next;
    }
};

Time Complexity:

Traversing the two linked lists takes O(max(m, n)) time, where m and n are the lengths of the linked lists. Creating a new linked list takes O(max(m, n)) time as well. Therefore, the time complexity of the solution is O(max(m, n)).

Space Complexity:

We create a new linked list whose length is at most max(m, n) + 1. Therefore, the space complexity of the solution is O(max(m, n)).

1