Sunday, January 4, 2015

Add Two Numbers (LeetCode Linked List)

Question: 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

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