Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Idea: Brute force. Keep adding if l1 or l2 is not empty or the carry is not 0. Keep a pointer pointing consistently to the head of the intended results, otherwise it is impossible to find the head of the result when the result is going to be returned : (
Time: O(n) Space: O(1)
Code:
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy=new ListNode(-1);
ListNode cur=dummy;
int carry=0;
while(l1!=null||l2!=null||carry!=0)
{
int valOne=0;
int valTwo=0;
if(l1!=null)
{
valOne=l1.val;
l1=l1.next;
}
if(l2!=null)
{
valTwo=l2.val;
l2=l2.next;
}
int sum=valOne+valTwo+carry;
carry=sum/10;
sum=sum%10;
cur.next=new ListNode(sum);
cur=cur.next;
}
return dummy.next;
}
}
No comments:
Post a Comment