Thursday, November 20, 2014

[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

思路:

从l1, l2头节点开始,对应位置相加并建立新节点。用一个变量carry记录进位。注意几种特殊情况:

1. 一个链表为空
l1:    NULL
l2:    1->2
sum: 1->2

2.  l1, l2长度不同,且结果有可能长度超过l1, l2中的最大长度
l1:    2->2
l2:    9->9->9
sum: 1->2->0->1



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode *dummy = new ListNode(0), *p = dummy;
        int carry = 0;
        while(l1 || l2 || carry) {
            if(l1) {
                carry+=l1->val;
                l1 = l1->next;
            }
            if(l2) {
                carry+=l2->val;
                l2 = l2->next;
            }
            p->next = new ListNode(carry%10);
            carry /= 10;
            p = p->next;
        }
        return dummy->next;
    }
};

1 comment: