题目：给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
C++
1.迭代：
直接从最低位开始模拟两个数相加，时间复杂度O（max（n,m）），空间复杂度O（m+n）
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *ans,*temp; ans=NULL; int tag=0; while(l1!=NULL&&l2!=NULL){ ListNode* p=new ListNode; p->val=l1->val+l2->val+tag; tag=0; if(p->val>=10){ p->val=p->val%10; tag=1; } p->next=NULL; if(ans==NULL) ans=p; else temp->next=p; temp=p; l1=l1->next; l2=l2->next; } while(l1!=NULL){ ListNode* p=new ListNode; p->val=l1->val+tag; tag=0; if(p->val>=10){ p->val=p->val%10; tag=1; } p->next=NULL; temp->next=p; temp=p; l1=l1->next; } while(l2!=NULL){ ListNode* p=new ListNode; p->val=l2->val+tag; tag=0; if(p->val>=10){ p->val=p->val%10; tag=1; } p->next=NULL; temp->next=p; temp=p; l2=l2->next; } if(tag){ ListNode* p=new ListNode; p->val=tag; p->next=NULL; temp->next=p; temp=p; } return ans; } };
总结：看题解有人添加了虚拟头结点，感觉很不错，学到了，学到了。
代码简化：后面的3个while可以放在一个while里面，很大程度上简化代码
2.递归
当时用迭代做出来已经感觉是时间空间最简了，后来看题解发现有人用了递归求解，两者殊途同归，这里带着训练的要求，写出如下代码。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: int c=0; ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { if(l1==NULL&&l2==NULL&&c==0)return NULL; //递归边界 l1!=NULL ? (c+=l1->val,l1=l1->next) :l1; l2!=NULL ? (c+=l2->val,l2=l2->next) :l2; ListNode * p=new ListNode; p->val=c%10; c=c/10; p->next=addTwoNumbers(l1,l2); return p; } };
加上递归和三目运算符确实很简洁
Python
1.迭代
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: tag=0 ans=ListNode(0) cur=ans while l1 or l2 or tag: if l1: tag+=l1.val l1=l1.next if l2: tag+=l2.val l2=l2.next cur.next=ListNode(tag%10) tag=tag//10 cur=cur.next return ans.next
2.递归
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def addTwoNumbers(self, l1, l2): def add(a,b,carry): if not (a or b): return ListNode(1) if carry else None a = a if a else ListNode(0) b = b if b else ListNode(0) val = a.val + b.val + carry carry = 1 if val>=10 else 0 a.val = val%10 a.next = add(a.next,b.next,carry) return a return add(l1,l2,0)
java
迭代
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; this.next=null;} * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode ans=new ListNode(0); ListNode cur=ans; int tag=0; while(l1!=null||l2!=null||tag!=0){ tag+= l1!=null ? l1.val:0; tag+= l2!=null ? l2.val:0; ListNode p=new ListNode(tag%10); tag=tag/10; cur.next=p; cur=p; l1= l1!=null? l1.next:l1; l2= l2!=null? l2.next:l2; } return ans.next; } }
递归
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; this.next=null;} * } */ class Solution { int tag=0; public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if(l1==null && l2==null && tag==0)return null; tag+= l1!=null ? l1.val:0; tag+= l2!=null ? l2.val:0; ListNode p=new ListNode(tag%10); tag=tag/10; l1= l1!=null? l1.next:l1; l2= l2!=null? l2.next:l2; p.next=addTwoNumbers(l1,l2); return p; } }
