LeetCode2—Add Two Numbers

￡神魔★判官ぃ 2022-06-09 07:36 143阅读 0赞

本类型博客中的各算法的时间复杂度分析均为博主自己推算，本类型博客也是博主自己刷LeetCode的自己的一些总结，因此个中错误可能较多，非常欢迎各位大神在博客下方评论，请不吝赐教

#     #

# 一、问题 #

*  输入：两个链表l1和l2，其中每个节点存储一个整数的某一位，从链表头开始依次位数升高
 *  输出：计算两个链表表示的整数的和，并将结果表示成链表输出

# 二、输入输出示例 #

*  输入：l1: 2->3->5, l2: 3->7->2
 *  输出：5->0->8

# 三、解法 #

本题的基本思路就是两个数加法的竖式计算。从低位到高位，对应位相加，如果大于10则向前进位，因此每个数位上的数=加数1对应位的数+加数2对应位的数+进位。由于遍历一遍即可，因此该题的解法的时间复杂度都是 O(n)

## 解法一：两个数同时遍历，中间不中断 ##

**解题思路**：由于两个数的位数可能不同，因此遍历过程中可能会出现一个已经遍历结束，而另一个还有好多位没有处理。此时可以将位数较少的数高位填0，使其和另一个数位数相等，这样做算法较为简单，但是实际上增加了一些不必要的运算

package com.happy.leetcode.p2;
    
    import com.happy.leetcode.util.ListNode;
    
    /**
     * 64.08%
     * @author bird
     *
     */
    public class AddTwoNumbersV1 {
        
        public static void main(String[] args) {
            int[] n1 = {1};
            int[] n2 = {9, 9};
            AddTwoNumbersV1 ins = new AddTwoNumbersV1();
            ListNode l1 = ins.generateNodeByArray(n1);
            ListNode l2 = ins.generateNodeByArray(n2);
            ins.printListNode(l1);
            ins.printListNode(l2);
            ins.printListNode(ins.addTwoNumbers(l1, l2));
        }
        
        private ListNode generateNodeByArray(int[] nums) {
            ListNode result = new ListNode(nums[nums.length-1]);
            ListNode tmp;
            for(int i=nums.length-2; i>=0; i--) {
                tmp = result;
                result = new ListNode(nums[i]);
                result.next = tmp;
            }
            return result;
        }
        
        private void printListNode(ListNode listNode) {
            while(listNode!=null) {
                System.out.print(listNode.val+"  ");
                listNode = listNode.next;
            }
            System.out.println();
        }
    
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if(l1==null && l2==null) {
                return null;
            }
            if(l1==null) {
                return l2;
            }
            if(l2==null) {
                return l1;
            }
            
            int bitResult = l1.val+l2.val;
            int carry = bitResult/10;
            ListNode result = new ListNode(bitResult%10);
            ListNode last = result;
            ListNode next = null;
            l1 = l1.next;
            l2 = l2.next;
            int left = 0;
            int right = 0;
            while(l1!=null || l2!=null || carry!=0) {
                if(l1!=null) {
                    left = l1.val;
                    l1 = l1.next;
                }else {
                    left = 0;
                }
                if(l2!=null) {
                    right = l2.val;
                    l2 = l2.next;
                }else {
                    right = 0;
                }
                bitResult = left+right+carry;
                carry = bitResult/10;
                next = new ListNode(bitResult%10);
                last.next = next;
                last = next;
            }
            return result;
        }
    
    }

**时间复杂度分析**：遍历次数等于位数较多的那个数，因此时间复杂度位 **O(max(n, m))**

## 解法二：先遍历位数较少的数，另起循环遍历另一个数剩下的位数 ##

**解题思路**：该解法中先同时遍历两个数，直到某一个数的位数用尽了。然后另起循环，遍历另一个数的剩余位，计算它们与进位相加后的结果。这样可以减少一些不必要的运算。另外在第二次遍历时，一旦在某位上进位终止了，即进位为0，而不是1时，则剩余的没有遍历的必要了，直接将剩余部分续接到结果链表末尾即可。

package com.happy.leetcode.p2;
    
    
    import com.happy.leetcode.util.ListNode;
    
    
    /**
     * 64.08%
     * @author bird
     *
     */
    public class AddTwoNumbersV2 {
        
        public static void main(String[] args) {
            int[] n1 = {8, 6};
            int[] n2 = {6, 4, 8};
            AddTwoNumbersV2 ins = new AddTwoNumbersV2();
            ListNode l1 = ins.generateNodeByArray(n1);
            ListNode l2 = ins.generateNodeByArray(n2);
            ins.printListNode(l1);
            ins.printListNode(l2);
            ins.printListNode(ins.addTwoNumbers(l1, l2));
        }
        
        private ListNode generateNodeByArray(int[] nums) {
            ListNode result = new ListNode(nums[nums.length-1]);
            ListNode tmp;
            for(int i=nums.length-2; i>=0; i--) {
                tmp = result;
                result = new ListNode(nums[i]);
                result.next = tmp;
            }
            return result;
        }
        
        private void printListNode(ListNode listNode) {
            while(listNode!=null) {
                System.out.print(listNode.val+"  ");
                listNode = listNode.next;
            }
            System.out.println();
        }
    
    
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if(l1==null && l2==null) {
                return null;
            }
            if(l1==null) {
                return l2;
            }
            if(l2==null) {
                return l1;
            }
            
            int bitResult = l1.val+l2.val;
            int carry = 0;
            ListNode result = new ListNode(bitResult);
            if(bitResult>=10) {
                carry = 1;
                result = new ListNode(bitResult-10);
            }
            ListNode last = result;
            ListNode next = null;
            l1 = l1.next;
            l2 = l2.next;
            while(l1!=null && l2!=null) {
                bitResult = l1.val+l2.val+carry;
                if(bitResult>=10) {
                    carry = 1;
                    next = new ListNode(bitResult-10);
                }else {
                    carry = 0;
                    next = new ListNode(bitResult);
                }
                last.next = next;
                last = next;
                l1 = l1.next;
                l2 = l2.next;
            }
            while(l1!=null) {
                if(carry==0) {
                    last.next = l1;
                    break;
                }
                bitResult = l1.val+carry;
                l1 = l1.next;
                if(bitResult>=10) {
                    carry = 1;
                    next = new ListNode(bitResult-10);
                }else {
                    carry = 0;
                    next = new ListNode(bitResult);
                }
                last.next = next;
                last = next;
            }
            while(l2!=null) {
                if(carry==0) {
                    last.next = l2;
                    break;
                }
                bitResult = l2.val+carry;
                l2 = l2.next;
                if(bitResult>=10) {
                    carry = 1;
                    next = new ListNode(bitResult-10);
                }else {
                    carry = 0;
                    next = new ListNode(bitResult);
                }
                last.next = next;
                last = next;
            }
            if(carry>0) {
                next = new ListNode(carry);
                last.next = next;
            }
            return result;
        }
    
    
    }

**时间复杂度分析**：时间复杂度同上，为 **O(max(n, m))**

##        ##