LeetCode Add Two Numbers: Simulate Addition With Linked List

Overview

LeetCode Add Two Numbers is a direct simulation of addition, be careful about the carry which could be added into the more significant digit.

LeetCode Add Two Numbers

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

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Analysis: Simulate Addition With Linked List

There is no tricky algorithm involved in this problem. The solution is straightforward by directly simulation of addition. The only things need to be kept in our mind is the following cases:

  1.   4->NULL + 6->NULL == 0->1->NULL
  2.   1-NULL + 9->9->9->NULL == 0->0->0->1->NULL

The following code is accepted by LeetCode OJ to pass this Add Two Numbers problem:

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    int sum = 0;
    int carry = 0;
    int lValue = 0;
    int rValue = 0;

    ListNode s(0);
    ListNode *p = &s;

    while (l1 || l2) {
        lValue = (NULL != l1) ? l1->val : 0;
        rValue = (NULL != l2) ? l2->val : 0;

        sum = lValue + rValue + carry;
        carry = sum / 10;
        sum %= 10;

        p->next = new ListNode(sum);
        p = p->next;
        if (l1) 
            l1 = l1->next;
        if (l2) 
            l2 = l2->next;
    }

    if (carry) 
        p->next = new ListNode(carry);
    return s.next;
}

Summary

LeetCode Add Two Numbers is a direct simulation of addition, be careful about the carry which could be added into the more significant digit.

Written on January 16, 2015