Add Two Numbers
You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
http://www.lintcode.com/en/problem/add-two-numbers/
Solution
比较简单,注意进位就行了。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
/**
* @param l1: the first list
* @param l2: the second list
* @return: the sum list of l1 and l2
*/
ListNode *addLists(ListNode *l1, ListNode *l2) {
// write your code here
ListNode result = ListNode(-1);
ListNode *cur = &result;
ListNode *digit;
int sumNode;
int incr = 0;
while (l1 && l2) {
sumNode = l1->val + l2->val + incr;
if(sumNode < 10) {
digit = new ListNode(sumNode);
cur->next = digit;
incr = 0;
} else {
digit = new ListNode(sumNode - 10);
cur->next = digit;
incr = 1;
}
l1 = l1->next;
l2 = l2->next;
cur = cur->next;
}
while (l1) {
sumNode = l1->val + incr;
if(sumNode < 10) {
digit = new ListNode(sumNode);
cur->next = digit;
incr = 0;
} else {
digit = new ListNode(sumNode - 10);
cur->next = digit;
incr = 1;
}
l1 = l1->next;
cur = cur->next;
}
while (l2) {
sumNode = l2->val + incr;
if(sumNode < 10) {
digit = new ListNode(sumNode);
cur->next = digit;
incr = 0;
} else {
digit = new ListNode(sumNode - 10);
cur->next = digit;
incr = 1;
}
l2 = l2->next;
cur = cur->next;
}
if(incr == 1) {
digit = new ListNode (incr);
cur->next = digit;
}
return result.next;
}
};
A more clean code.
class Solution {
public:
/**
* @param l1: the first list
* @param l2: the second list
* @return: the sum list of l1 and l2
*/
ListNode *addLists(ListNode *l1, ListNode *l2) {
// write your code here
ListNode result = ListNode(-1);
ListNode *cur = &result;
ListNode *digit;
int sumNode;
int incr = 0;
while (l1 || l2) {
int num1 = l1 ? l1->val : 0;
int num2 = l2 ? l2->val:0;
sumNode = num1 + num2 + incr;
digit = new ListNode(sumNode%10);
cur->next = digit;
cur = cur->next;
incr = sumNode/10;
if(l1) l1 = l1->next;
if(l2) l2 = l2->next;
}
if(incr == 1) {
digit = new ListNode (incr);
cur->next = digit;
}
return result.next;
}
};