Coding Exercise – Add Two Numbers on Singly-Linked List

Question: 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 contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

The C++ definition of a singly-linked list:

1
2
3
4
5

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

One solution will be to transform each singly-list into a integer, add both up and then transform back to a singly-list. However, this is not the simplest and easiest way. We notice that the number is in reverse order in a singly linked-list, therefore we can add digits by digits when walking through both list. Just remember to add the carry when the sum of two digits is more than 9.

The head pointer of the result list should be preserved. We create a dummy head pointer and return its next when exiting the function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = new ListNode(0), *prev = head;
        int c = 0;
        while (l1 != NULL || l2 != NULL) {
            int sum = c + (l1 ? l1->val : 0) + (l2 ? l2->val : 0);
            c = sum / 10;
            prev->next = new ListNode(sum % 10);
            prev = prev->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }      
        if (c > 0) {
            prev->next = new ListNode(c);
        }
        return head->next;
    }
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = new ListNode(0), *prev = head;
        int c = 0;
        while (l1 != NULL || l2 != NULL) {
            int sum = c + (l1 ? l1->val : 0) + (l2 ? l2->val : 0);
            c = sum / 10;
            prev->next = new ListNode(sum % 10);
            prev = prev->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }      
        if (c > 0) {
            prev->next = new ListNode(c);
        }
        return head->next;
    }
};

Assume the length of both list are A and B, the overall runtime complexity is O(A+B), obviously.

You may also like: 编程练习题: 对两单向链表求和

–EOF (The Ultimate Computing & Technology Blog) —