动图《两个数相加》小学生都能看懂本文转载请联系程序员小雄公众号。前言大家好，我是华为程序员小熊。今天给大家带来一道在各大互联网公司面试中经常考到的链表相关的中档题，也就是里口第二题——双数相加。本文主要介绍迭代+虚拟头节点的策略来回答这个问题，供大家参考，希望对大家有所帮助。添加两个数字会得到两个非空链表，表示两个非负整数。它们的每一个数字都是倒序存储的，每个节点只能存储一个数字。请将两个数字相加并以相同的形式返回表示总和的链表。你可以假设这两个数字都不会以数字0以外的0开头。示例1其他示例和提示解题思路由于标题清楚地告诉每个节点只能存储一个数字，当数字之和两个链表中相同位置大于10，需要考虑进位问题。两个链表的例子：l1=[3,4,3],l2=[5,6,4]。当他们的第二个节点的编号相加时，第三个节点的编号之和需要进1。由于需要遍历两个链表，所以考虑了迭代的思想。注意点1，考虑中间位进位的问题；例如l1=[3,4,3]，l2=[5,6,4]。2.考虑携带最高位的问题。例如l1=[9,9,9,9,9,9,9]，l2=[9,9,9,9]。以l1=[3,4,3],l2=[5,6,4]为例，如下图所示：示例不断遍历两个链表，将节点处的值相加相同的位置，并更新到新的链表；添加和更新相同位置的节点的值。当需要进位时，保留需要进位的值；当需要进位时，先保留进位。最后一个进位的值加到两个链表当前节点的和上；CarryUpdate完整的处理过程，如下图所示：将两个链表的节点值相加并更新到新的链表，完整的处理过程ShowmetheCode「C」structListNode*addTwoNumbers(structListNode*l1,structListNode*l2){structListNode*dummyHead=(structListNode*)malloc(sizeof(structListNode));dummyHead->val=0;dummyHead->next=NULL;structListNode*node=dummyHead;intcarry=0;//进位/*遍历两个链表*/for(structListNode*p=l1,*q=l2;p!=NULL||q!=NULL;){/*相同位置的节点值之和*/intsum=carry;sum+=(p!=NULL)?p->val:0;sum+=(q!=NULL)?q->val:0;/*不断更新两个链接相同位置的sum值列出新链表*/node->next=(structListNode*)malloc(sizeof(structListNode));node=node->next;node->val=sum%10;node->next=NULL;/*进位处理，连续遍历两个链表*/carry=sum/10;p=(p==NULL)?p:p->next;q=(q==NULL)?q:q->next;}/*如果总和最高bits大于10，加一位，新链表的节点值为1*/if(carry!=0){node->next=(structListNode*)malloc(sizeof(structListNode));node=node->next;node->val=1;node->next=NULL;}returndummyHead->next;}「C++」ListNode*addTwoNumbers(ListNode*l1,ListNode*l2){ListNode*dummyHead=newListNode(0);ListNode*node=dummyHead;intcarry=0;for(ListNode*p=l1,*q=l2;p!=nullptr||q!=nullptr;){intsum=carry;sum+=(p==nullptr)?0:p->val;sum+=(q==nullptr)?0:q->val;node->next=newListNode(sum%10);node=node->next;carry=sum/10;p=(p==nullptr)?p:p->next;q=(q==nullptr)?q:q->next;}if(carry!=0){node->next=newListNode(carry);}returndummyHead->next;}「Java」ListNodeaddTwoNumbers(ListNode1,ListNode2){ListNodedummyHead=newListNode(-1);ListNodecur=dummyHead;intcarry=0;while(l1!=null||l2!=null){intsum=carry;sum+=(l1==null)?0:l1.val;sum+=(l2==null)?0:l2.val;cur.next=newListNode(sum%10);cur=cur.next;carry=sum/10;l1=(l1==null)?l1:l1.next;l2=(l2==null)?l2:l2.next;}if(carry!=0){cur.next=newListNode(carry);}returndummyHead.next;}「Python3」defaddTwoNumbers(self,l1:ListNode,l2:ListNode)->ListNode:dummyHead=ListNode(0)node=dummyHeadcarry=0while(l1orl2):sum=carryif(l1):sum+=l1.vall1=l1.nextifl2:sum+=l2.vall2=l2.nextnode.next=ListNode(sum%10)node=node.nextcarry=sum//10ifcarry!=0:node.next=ListNode(carry)returndummyHead.next「Golang」funcaddTwoNumbers(l1*ListNode,l2*ListNode)*ListNode{dummy:=new(ListNode)node:=dummycarry:=0forl1!=nil||l2!=nil{sum:=carryifl1!=nil{sum+=l1.Vall1=l1.Next}ifl2!=nil{sum+=l2.Vall2=l2.Next}node.Next=new(ListNode)node=node.Nextnode.Val=sum%10carry=sum/10}ifcarry!=0{node.Next=&ListNode{Val:carry}}returndummy.Next}复杂度分析时间复杂度：O(max(m,n))，其中m和n是两个的长度链表需要递归调用两个链表的每个节点一次。空间复杂度：O(1)，没有额外开辟存储空间。
