Ambitor 发表于2年前
• 发表于 2年前
• 阅读 49
• 收藏 0
• 评论 0

### 题目

Total Accepted: 137297　　Total Submissions: 599150　　Difficulty: Medium

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

Subscribe to see which companies asked this question

### 代码

``````    /**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1==null||l2==null)return null;
int multiple=0;
ListNode result=null,nextNode=null;//用来表示结果与下一个Node
while(l1!=null){
int n1=0,n2=0,sum=0;
n1= l1.val;
if(l2!=null){
n2= l2.val;
sum=n1+n2;
sum+=multiple;
multiple=0;
if(sum>9){
multiple=sum/10;
sum=sum%10;
}
if(result==null){
result=new ListNode(sum);
nextNode=result;
}
else{
nextNode.next=new ListNode(sum);
nextNode=nextNode.next;
}
l2=l2.next;//l2的指针随l1偏移
l1=l1.next;
}else{
n1+=multiple;
multiple=0;
if(n1>9){
multiple=n1/10;
n1=n1%10;
}
nextNode.next=new ListNode(n1);
nextNode=nextNode.next;
l1=l1.next;
}
}
while(l2!=null){//如果l1链表长度少于l2链表长度
int n2= l2.val;
n2+=multiple;
multiple=0;
if(n2>9){
multiple=n2/10;
n2=n2%10;
}
nextNode.next=new ListNode(n2);
nextNode=nextNode.next;
l2=l2.next;
}
if(multiple!=0){//迭代完Node1、Node2 最后如果进位不为0 则加一位
nextNode.next=new ListNode(multiple);
nextNode=nextNode.next;
}
return result;
}
}``````

O(n)的时间 O(n)的内存

×