Add Two Numbers

1package pkg5leetcode.interview150;2 3/*4 * Add Two Numbers | LC 25 * APPROACH: Walk both lists with carry; build result digit by digit.6 * COMPLEXITY: Time O(n), Space O(1) excluding output7 */8public class interview150_LC2AddTwoNumbers {9    /** Same shape as pkg5leetcode/common/ListNode.java (nested for single-file runs). */10 11    static class ListNode {12        int val;13        ListNode next;14        ListNode(int val) { this.val = val; }15    }16 17    static ListNode addTwoNumbers(ListNode l1, ListNode l2) {18        ListNode dummy = new ListNode(0), tail = dummy;19        int carry = 0;20        while (l1 != null || l2 != null || carry != 0) {21            int sum = carry;22            if (l1 != null) { sum += l1.val; l1 = l1.next; }23            if (l2 != null) { sum += l2.val; l2 = l2.next; }24            tail.next = new ListNode(sum % 10);25            tail = tail.next;26            carry = sum / 10;27        }28        return dummy.next;29    }30 31    static ListNode of(int... vals) {32        ListNode dummy = new ListNode(0), cur = dummy;33        for (int v : vals) { cur.next = new ListNode(v); cur = cur.next; }34        return dummy.next;35    }36 37    static int[] toArray(ListNode head) {38        java.util.List<Integer> list = new java.util.ArrayList<>();39        while (head != null) { list.add(head.val); head = head.next; }40        return list.stream().mapToInt(Integer::intValue).toArray();41    }42 43    public static void main(String[] args) {44        check(java.util.Arrays.equals(toArray(addTwoNumbers(of(2, 4, 3), of(5, 6, 4))), new int[]{7, 0, 8}), "case1");45        check(java.util.Arrays.equals(toArray(addTwoNumbers(of(0), of(0))), new int[]{0}), "case2");46        System.out.println("all tests passed");47    }48 49    static void check(boolean cond, String name) {50        if (!cond) throw new AssertionError("FAILED: " + name);51        System.out.println("  PASS " + name);52    }53}