C++LeetCode每日一题 - 2. 两数相加

题目：2.两数相加

Description

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

Sample

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807

Solution

首先将两条链表合并成一条链表，再进行进位运算，使得链表每个节点只能存储一位数字。

具体操作：双指针，各一个指针指向每条链表的头节点，如果都不为空，将第二条链表的节点的值加到第一条节点的值上，在一起往后移动。如果出现指向空，直接将上次的指针指向不为空的，结束遍历。如果都为空，直接结束遍历。 这样就将两条链表合并成了一条链表。 然后遍历得到的链表，若当前节点的值大于等于10，就会产生进位，那么下个节点的值加1。直到最后一个节点，若最后一个节点的值大于等于10，就要创建一个新的节点，赋值为1。至此，完成进位运算。 返回最初的头节点即可！

AC Code

class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode * h1=l1; ListNode * h2=l2; ListNode * pos=NULL; ListNode * t; while(h1||h2){//合并链表 if(h1&&h2){ h1->val+=h2->val; if(pos==NULL) pos=h1; else { pos->next=h1; pos=pos->next; } } else { if(h1==NULL&&h2){ pos->next = h2; pos=pos->next; } if(h2==NULL&&h1){ pos->next = h1; pos=pos->next; } break; } if(h1) h1=h1->next; if(h2) h2=h2->next; } h1=l1; int num=0;//记录进位 while(h1){ h1->val+=num; if(h1->val>=10){ num=1; h1->val%=10; } else num=0; if(h1->next==NULL&&num){//考虑最后一个节点可进位 t=new ListNode(1); num=0; h1->next=t; } h1=h1->next; } return l1; } };

PS：希望对你有帮助！