Leetcode算法Java全解答--002. 两数相加

秒速五厘米 2022-05-08 02:12 145阅读 0赞

# Leetcode算法Java全解答–002. 两数相加 #

### 文章目录 ###

*  Leetcode算法Java全解答--002. 两数相加
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

1.  两数相加

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出：7 -> 0 -> 8
    原因：342 + 465 = 807

## 想法 ##

1.  从左到右对链表进行迭代
2.  位置相对应的2个数字相加，10为除数，商为进位，余数为新链表当前位置的数据
3.  此时应考虑相加是否会进位
4.  注意空指针异常问题

## 结果 ##

时间复杂度：n  
空间复杂度：1  
执行用时：63 ms  
效率排名：超过24.72%的答案

## 总结 ##

1.  只需使用一个链表变量就可以解决的问题，我多加了2个ListNode result
2.  进位数carry我使用了布尔类型，我感觉是没什么差距的，因为最多进位就是1

## 代码 ##

### 我的答案 ###

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode next1 = l1;
            ListNode next2 = l2;
            int count = 0;
            boolean carry = false;
        
            ListNode result = new ListNode(0);
            ListNode runResult = result;
        
            ListNode preNode = result;
        
            while (next1 != null || next2 != null) {
              int val1 = next1 == null ? 0 : next1.val;
              int val2 = next2 == null ? 0 : next2.val;
        
              int tmp = val1 + val2;
              if (carry) {
                tmp++;
              }
        
              int nodeVal = tmp % 10;
              carry = tmp >= 10;
        
              if (count == 0) {
                runResult.val = nodeVal;
              } else {
                runResult = new ListNode(nodeVal);
              }
              preNode.next = runResult;
        
              next1 = next1 == null ? null : next1.next;
              next2 = next2 == null ? null : next2.next;
              preNode = runResult;
              runResult = runResult.next;
              count++;
            }
        
            if (carry) {
              preNode.next = new ListNode(1);
              preNode = preNode.next;
            }
            preNode.next = null;
        
            return result;
    
      }

### 大佬们的答案 ###

public ListNode better(ListNode l1, ListNode l2) {
    
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
          int x = (p != null) ? p.val : 0;
          int y = (q != null) ? q.val : 0;
          int sum = carry + x + y;
          carry = sum / 10;
          curr.next = new ListNode(sum % 10);
          curr = curr.next;
          if (p != null) {
            p = p.next;
          }
          if (q != null) {
            q = q.next;
          }
        }
        if (carry > 0) {
          curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    
      }

### 测试用例 ###

@Test
      public void test002() {
        // 创建测试案例
        ListNode listNode1 = new ListNode(5);
        ListNode listNode2 = new ListNode(6);
        ListNode listNode3 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
    
        ListNode listNode21 = new ListNode(2);
        ListNode listNode22 = new ListNode(4);
        ListNode listNode23 = new ListNode(3);
        listNode21.next = listNode22;
        listNode22.next = listNode23;
    
        ListNode listNode31 = new ListNode(1);
        ListNode listNode32 = new ListNode(1);
    
        // 测试案例期望值
        Integer[] expResult1 = new Integer[] { 7, 0, 8 };
        Integer[] expResult3 = new Integer[] { 2 };
    
    
        // 执行方法
        Solution2 solution2 = new Solution2();
        ListNode result1 = solution2.addTwoNumbers(listNode1, listNode21);
        ListNode result3 = solution2.addTwoNumbers(listNode31, listNode32);
        // 判断期望值与实际值
        Assert.assertArrayEquals(expResult1, result1.toArray().toArray());
        Assert.assertArrayEquals(expResult3, result3.toArray().toArray());
    
      }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan