O(n) time No extra Space Java Solution


  • 0
    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if(l1==null) return l2;
            if(l2==null) return l1;
            int len1=length(l1), len2=length(l2);
            ListNode dummy=new ListNode(0);
            int idx=Math.max(len1,len2);
            ListNode ptr1=l1, ptr2=l2;
            while(idx>0){
                int sum=0;
                if(idx<=len1) {sum+=ptr1.val;ptr1=ptr1.next;}
                if(idx<=len2) {sum+=ptr2.val;ptr2=ptr2.next;}
                ListNode tmp=dummy.next;
                dummy.next=new ListNode(sum);
                dummy.next.next=tmp;
                idx--;
            }
            ListNode ptr=dummy.next;
            int remain=0;
            while(ptr!=null){
                int old=ptr.val;
                old+=remain;
                ptr.val=old%10;
                remain=old/10;
                ptr=ptr.next;
            }
            ListNode head=reverse(dummy.next);
            if(remain!=0){
                ListNode added=new ListNode(remain);
                added.next=head;
                return added;
            }else return head;
        }
        
        public int length(ListNode node){
            ListNode ptr=node;
            int count=0;
            while(ptr!=null){
                count++;
                ptr=ptr.next;
            }
            return count;
        }
        
        public ListNode reverse(ListNode head){
            ListNode p=head, q=head.next;
            head.next=null;
            while(q!=null){
                ListNode tmp=q.next;
                q.next=p;
                p=q;
                q=tmp;
            }
            return p;
        }
    }
    

Log in to reply
 

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