描述

You are given two linked lists representing two non-negative numbers. 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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8


分析：342+465=807——>708


Add.h

#pragmaonce#include<iostream>usingnamespacestd;typedefstructListNode{int_var;ListNode*_next;ListNode(intvar):_var(var),_next(NULL){}}node,*node_p;classSolution{public:node_padd_two_number(ListNode*l1,ListNode*l2){node_pNewHead=NULL;node_ppa=l1->_next;node_ppb=l2->_next;intmod=0;while(pa!=NULL||pb!=NULL){inta=0;intb=0;if(pa!=NULL)a=pa->_var;if(pb!=NULL)b=pb->_var;intret=(a+b+mod)%10;mod=(a+b+mod)/10;node_ptmp=newnode(ret);tmp->_next=NewHead;NewHead=tmp;if(pa!=NULL)pa=pa->_next;if(pb!=NULL)pb=pb->_next;}if(mod>0){node_ptmp=newnode(mod);tmp->_next=NewHead;NewHead=tmp;}returnNewHead;}};

Add.cpp

#include"Add_List.h"#include<stdlib.h>usingnamespacestd;intmain(){Solutions1;node_pl1=newnode(-1);node_ppa=l1;pa->_next=newnode(4);pa=pa->_next;pa->_next=newnode(6);pa=pa->_next;pa->_next=newnode(7);pa=pa->_next;pa->_next=newnode(8);node_pl2=newnode(-1);node_ppb=l2;pb->_next=newnode(1);pb=pb->_next;pb->_next=newnode(2);pb=pb->_next;pb->_next=newnode(5);pb=pb->_next;pb->_next=newnode(6);pb=pb->_next;pb->_next=newnode(3);node_pret=s1.add_two_number(l1,l2);system("pause");return0;}

调试查看结果：


// LeetCode, Add Two Numbers

// 时间复杂度 O(m+n)，空间复杂度 O(1)

classSolution{public:ListNode*addTwoNumbers(ListNode*l1,ListNode*l2){ListNodedummy(-1);//头节点intcarry=0;ListNode*prev=&dummy;for(ListNode*pa=l1,*pb=l2;pa!=nullptr||pb!=nullptr;pa=pa==nullptr?nullptr:pa->next,pb=pb==nullptr?nullptr:pb->next,prev=prev->next){constintai=pa==nullptr?0:pa->val;constintbi=pb==nullptr?0:pb->val;constintvalue=(ai+bi+carry)%10;carry=(ai+bi+carry)/10;prev->next=newListNode(value);//尾插法}if(carry>0)prev->next=newListNode(carry);returndummy.next;}};


《完》