Easy to understand O(n) naive approach using array


  • 1
    V
    class Solution {
        public int getLen(ListNode l1){
            int len=0;
            while(l1!=null){
                l1=l1.next;
                len++;
            }
            return len;
        }
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            //get length of lists
            int lenl1=getLen(l1);
            int lenl2=getLen(l2);
            //create array of size 1 more than larger one..1 more for carry
            int size=(lenl1>lenl2) ? lenl1+1 : lenl2+1;
            int[] newarr=new int [size];
            int i=size-lenl1;
            //Insert all elements of list to array while adding the content already present
            while(i<size){
                newarr[i]+=l1.val;
                if(l1!=null)l1=l1.next;
                i++;
            }
            i=size-lenl2;
            while(i<size){
                newarr[i]+=l2.val;
                if(l2!=null)l2=l2.next;
                i++;
            }
           //iterate through array, add carry content
            for(i=size-1;i>0;i--){
              if(newarr[i]>9){
                  newarr[i-1]+=newarr[i]/10;
                  newarr[i]=newarr[i]%10;
                }
            }
           //convert array to ListNode
            int start=(newarr[0]==0)?1:0;
            ListNode head = new ListNode(0);
            ListNode temp=head;
            for(i=start;i<size;i++){
                head.next=new ListNode(newarr[i]);
                head=head.next;
            }
            return temp.next;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.