示例1:
方法一:
将两个链表中较短的一个进行补零,之后对应相加
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { // 为了实现链表的(逆向)两数相加,首先需要统一数据格式,即将两链表位数补齐; // 而要想补齐位数,需要首先统计链表的各自长度 int len1 = 1; int len2 = 1;//记录链表长度 ListNode* p = l1; ListNode* q = l2;//链表的移动指针 //首先计算链表的长度 while (p->next != NULL){ len1 ++; p = p->next; } while (q->next != NULL){ len2 ++; q = q->next; } //为较短的一个链表补零 if (len1 >len2){//为l2补零 for (int i=0; i<len1-len2; i++){ q->next = new ListNode(0); q = q->next; } } else{//为l1补零 for (int i=0; i<len2-len1; i++){ p->next = new ListNode(0); p = p->next; } } //将两数相加 p = l1; q = l2; ListNode* l3 = new ListNode(-1); ListNode* w = l3; bool flag = false;//是否进位 int sum; for (int i=0; i<len1 || i<len2; i++){//两链表长度相同,从低到高遍历每一个数码进行相加,考虑进位问题 sum = flag + p->val + q->val; flag = sum>9?true:false; w->next = new ListNode(sum%10); w = w->next; p = p->next; q = q->next; } if (flag){//若最高位仍进行进位 w->next = new ListNode(1); } l3 = l3->next; return l3; } };
方法二:
不进行对齐补零
// Solution 2: class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* head = new ListNode(-1);//待输出链表 ListNode* h = head;//可移动的指针 int sum;//存储相加结果 bool flag = false;//是否进位的标志 while(l1!=NULL || l2!=NULL){ sum = 0 + flag;//每次使用时归零处理,同时考虑来自上一位的进位 if(l1 != NULL){ sum += l1->val; l1 = l1->next; } if (l2 != NULL){ sum += l2->val; l2 = l2->next; } h->next = new ListNode(sum%10); h = h->next; flag = sum>9?true:false; } if (flag){ h->next = new ListNode(1); } head = head->next; return head; } };
注:以上代码为本人根据网友高赞题解编写,略有改动,并非原创