Java O(n) runtime beats 94%


  • 0
    N
    public class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            // get the length of two list 
            int len1 = 1, len2 = 1;
            ListNode n1 = l1, n2 = l2;
            while ((n1 = n1.next) != null) len1++;
            while ((n2 = n2.next) != null) len2++;
            // create two arrays to store elements 
            // ‘+1’ to store the overflow number
            int[] a1 = new int[len1+1], a2 = new int[len2+1];
            for (int i = len1 - 1; i >= 0; i--){
                a1[i] = l1.val;
                l1 = l1.next;
            }
            for (int i = len2 - 1; i >= 0; i--){
                a2[i] = l2.val;
                l2 = l2.next;
            }
            // choose the longer array as the result of add
            int[] a = len1 < len2 ? a2 : a1;
            // add two arrays from tail to head
            for (int i = 0; i < Math.max(len1, len2); i++){
                int sum = 0;
                if (i < len1) sum += a1[i];
                if (i < len2) sum += a2[i];
                a[i] = sum % 10;
                a[i+1] += sum / 10;
            }
            // create the result list
            ListNode res, temp;
            if (a[a.length-1] > 0){
                res = new ListNode(1);
                res.next = new ListNode(a[a.length-2]);
                temp = res.next;
            }else{
                res = new ListNode(a[a.length-2]);
                temp = res;
            }
            for (int i = a.length-3; i >= 0; i--){
                temp.next = new ListNode(a[i]);
                temp = temp.next;
            }
            return res;
        }
    }
    

Log in to reply
 

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