每日力扣：2. 两数相加

冷不防 2022-03-12 17:26 196阅读 0赞

package com.sample.suncht.algo;
    
    import com.google.common.base.Joiner;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 2. 两数相加
     * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
     *
     * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     *
     * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     *
     * 示例：
     *
     * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 0 -> 8
     * 原因：342 + 465 = 807
     *
     * 时间复杂度：max(O(l1), O(l2)), 空间复杂度：O(1)
     *
     * @author sunchangtan
     * @date 2019/3/1 13:07
     */
    public class AddTwoNumbers {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if(l1 == null && l2 == null) {
                return new ListNode(0);
            }
            if(l1 == null) {
                return l2;
            }
            if(l2 == null) {
                return l1;
            }
    
            ListNode result = new ListNode(0);
    
            ListNode n1 = l1;
            ListNode n2 = l2;
            ListNode nr = result;
            int carryNum = 0;
            while (n1 != null && n2 != null) {
                int val = n1.val + n2.val + carryNum;
                if(val > 9) {
                    nr.val = val - 10;
                    carryNum = 1;
                } else {
                    nr.val = val;
                    carryNum = 0;
                }
    
                n1 = n1.next;
                n2 = n2.next;
                if(n1 != null || n2 != null) {
                    nr.next = new ListNode(0);
                    nr = nr.next;
                }
            }
    
            while (n1 != null) {
                int val = n1.val + carryNum;
                if(val > 9) {
                    nr.val = val - 10;
                    carryNum = 1;
                } else {
                    nr.val = val;
                    carryNum = 0;
                }
    
    
                n1 = n1.next;
    
                if(n1 != null) {
                    nr.next = new ListNode(0);
                    nr = nr.next;
                }
            }
    
            while (n2 != null) {
                int val = n2.val + carryNum;
                if(val > 9) {
                    nr.val = val - 10;
                    carryNum = 1;
                } else {
                    nr.val = val;
                    carryNum = 0;
                }
    
                n2 = n2.next;
    
                if(n2 != null) {
                    nr.next = new ListNode(0);
                    nr = nr.next;
                }
            }
    
            if(carryNum > 0) {
                nr.next = new ListNode(carryNum);
            }
    
            return result;
        }
    
        public static void main(String[] args) {
            ListNode l1 = new ListNode(5);
    //        l1.next = new ListNode(4);
    //        l1.next.next = new ListNode(3);
    //        l1.next.next.next = new ListNode(6);
    //        l1.next.next.next.next = new ListNode(2);
    
            ListNode l2 = new ListNode(5);
    //        l2.next = new ListNode(6);
    //        l2.next.next = new ListNode(9);
    
            ListNode list = new AddTwoNumbers().addTwoNumbers(l1, l2);
            System.out.println(list.outResult());
        }
    
        public static class ListNode {
            int val;
            ListNode next;
    
            ListNode(int x) {
                val = x;
            }
    
            public String outResult() {
                List<Integer> list = new ArrayList<>();
                ListNode n = this;
                while (n != null) {
                    list.add(n.val);
                    n = n.next;
                }
    
                return Joiner.on("->").join(list);
            }
        }
    }