题目:
/*
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
*/
解决方案如下:
(以下代码包含了测试代码部分)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
// 为了方便测试,加入该方法,将数字转换成node
static ListNode *nodeWithNumber(int num) {
if (num == 0)
{
return new ListNode(0);
}
int rest = num / 10;
ListNode *head = new ListNode(num % 10);
ListNode *tail = head;
while (rest > 0)
{
ListNode *next = new ListNode(rest % 10);
tail->next = next;
tail = next;
rest = rest / 10;
}
return head;
}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if (l1 == nullptr)
{
return l2;
}
if (l2 == nullptr)
{
return l1;
}
int sum = 0;
ListNode *head = new ListNode(0);
ListNode *cur = head;
while (1)
{
if (l1 != nullptr)
{
sum += l1->val;
l1 = l1->next;
}
if (l2 != nullptr)
{
sum += l2->val;
l2 = l2->next;
}
cur->val = sum % 10;
sum = sum / 10;
if (l1 != nullptr || l2 != nullptr || sum)
{
cur->next = new ListNode(0);
cur = cur->next;
}
else
break;
}
return head;
}
};
void testNode();
void printNode(ListNode *node, bool result);
void printNode(ListNode *node);
void testNormal();
void testSpec();
#include "iostream"
int main() {
testNode();
testNormal();
testSpec();
system("pause");
return 0;
}
void testNode(){
ListNode *node1 = ListNode::nodeWithNumber(342);
ListNode *node2 = ListNode::nodeWithNumber(0);
printNode(node1);
printNode(node2);
printf("-----------------------------\n");
free(node1);
free(node2);
}
void testNormal() {
ListNode *node1 = ListNode::nodeWithNumber(342);
ListNode *node2 = ListNode::nodeWithNumber(465);
printNode(node1);
printNode(node2);
ListNode *result1 = Solution().addTwoNumbers(node1, node2);
printNode(result1, true);
printf("-----------------------------\n");
ListNode *node3 = ListNode::nodeWithNumber(32);
ListNode *node4 = ListNode::nodeWithNumber(465);
printNode(node3);
printNode(node4);
ListNode *result2 = Solution().addTwoNumbers(node3, node4);
printNode(result2, true);
printf("-----------------------------\n");
free(node1);
free(node2);
free(node3);
free(node4);
free(result1);
free(result2);
}
void testSpec() {
ListNode *node1 = ListNode::nodeWithNumber(0);
ListNode *node2 = ListNode::nodeWithNumber(465);
printNode(node1);
printNode(node2);
ListNode *result1 = Solution().addTwoNumbers(node1, node2);
printNode(result1, true);
printf("-----------------------------\n");
ListNode *node3 = ListNode::nodeWithNumber(342);
ListNode *node4 = ListNode::nodeWithNumber(0);
printNode(node3);
printNode(node4);
ListNode *result2 = Solution().addTwoNumbers(node3, node4);
printNode(result2, true);
printf("-----------------------------\n");
ListNode *result3 = Solution().addTwoNumbers(nullptr, node4);
printNode(result3, true);
printf("-----------------------------\n");
ListNode *result4 = Solution().addTwoNumbers(nullptr, nullptr);
printNode(result4, true);
printf("-----------------------------\n");
free(node1);
free(node2);
free(node3);
free(node4);
free(result1);
free(result2);
// 因为这里result3得到的就是node4,所以不需要释放result3
// result = nullptr
}
void printNode(ListNode *node) {
printNode(node, false);
}
void printNode(ListNode *node, bool result) {
if (node != nullptr)
{
ListNode *p = node;
int num = 0;
int i = 0;
while (p != nullptr)
{
if (i == 0)
{
num += p->val;
}
else
{
num += p->val * (int)pow(10, i);
}
i++;
printf("%d -> ", p->val);
p = p->next;
}
printf("NULL <<<< %s == %d\n", result?"result":"num", num);
}
else
{
printf("node is a nullptr!\n");
}
}
执行结果如下:
2 -> 4 -> 3 -> NULL <<<< result == 342
0 -> NULL <<<< result == 0
-----------------------------
2 -> 4 -> 3 -> NULL <<<< result == 342
5 -> 6 -> 4 -> NULL <<<< result == 465
7 -> 0 -> 8 -> NULL <<<< result == 807
-----------------------------
2 -> 3 -> NULL <<<< result == 32
5 -> 6 -> 4 -> NULL <<<< result == 465
7 -> 9 -> 4 -> NULL <<<< result == 497
-----------------------------
0 -> NULL <<<< result == 0
5 -> 6 -> 4 -> NULL <<<< result == 465
5 -> 6 -> 4 -> NULL <<<< result == 465
-----------------------------
2 -> 4 -> 3 -> NULL <<<< result == 342
0 -> NULL <<<< result == 0
2 -> 4 -> 3 -> NULL <<<< result == 342
-----------------------------
0 -> NULL <<<< result == 0
-----------------------------
node is a nullptr!
-----------------------------
请按任意键继续. . .
网友评论