LeetCode刷题笔记(Add Two Numbers)
刚刚刷了一道题,但是第一种方法获得的结果不是特别理想,所以还需要进一步改进,下面就和大家来分享一下经验吧!
题目如下:
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.
题意分析:
给定两个用于表示两个非负整数的非空链表,其中数是按逆序的方式挨个存放在链表中(即个十百千万....)。请将这两个正整数求和,并把和以逆序的方式存放在一个新链表中。
解答如下:
方法一(常规法)
遍历两个链表,分别求出两链表表示的整数,然后再对它们求和,最后将求和结果逆序存放在新链表中。
class Solution{
public:
ListNode* addTwoNumbers( ListNode* l1, ListNode* l2 ){
int count = 0;
int sum1 = 0;
int sum2 = 0;
ListNode* cur1 = l1;
ListNode* cur2 = l2;
while (cur1) {
sum1 = sum1 + cur1 -> val * pow(10, count); //将链表中的整数表示出来
count ++;
cur1 = cur1 -> next;
}
count = 0;
while (cur2) {
sum2 = sum2 + cur2 -> val * pow(10, count); //将链表中的整数表示出来
count ++;
cur2 = cur2 -> next;
}
long long sum = (long long) sum1 + (long long) sum2;
ListNode* dummy = new ListNode(-1); //创建新链表
ListNode* cur = dummy;
count = 0;
while ( sum / pow(10, count) > 1 || sum == 0){ //这里不能是>0,且需用sum == 0, 来约束链表节点只为0的情况
cur->next = new ListNode( int( sum / pow(10, count) ) % 10 ); //分别个十百千等位
count ++;
cur = cur -> next;
}
return dummy -> next;
}
};
提交后的结果如下:
方法二(两链表对应相加)
由于链表是逆序存放各个位的(第一个节点是个位),所以可以直接将两链表的对应节点值相加,若相加结果超过10则进位标志置1,再将超过10的部分与上次的进位标志求和并存放入新的链表节点中,若相加结果不超过10则直接与上次的进位标志求和并存放入新的链表节点中,最后还需要判断下进位标志是否为1,如果为1还需增加一个节点保存1值。
class Solution {
public:
ListNode* addTwoNumbers( ListNode* l1, ListNode* l2 ) {
ListNode *dummy = new ListNode(-1), *cur = dummy;
int carry = 0;
while (l1 || l2) {
int val1 = l1 ? l1->val : 0;
int val2 = l2 ? l2->val : 0;
int sum = val1 + val2 + carry;
carry = sum / 10;
cur->next = new ListNode(sum % 10);
cur = cur->next;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
if (carry) cur->next = new ListNode(1);
return dummy->next;
}
};
提交后的结果如下:
日积月累,与君共进,增增小结,未完待续。