devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

两数相加——LeetCode(解题过程略显艰辛且奇葩）_leetcode两数相加解法

作者：从前慢现在也慢 | 2024-08-04 19:17:41

赞

踩

leetcode两数相加解法

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

在这里插入图片描述

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

  • 1
  • 2
  • 3
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers

比较粗心看漏了几次题目，导致多次出错。

几次出错

  • 第一次没看到编译器里需要用它提供的链表进行编码，直接用了Java自带的List<>，在IDEA中写完准备复制到编译器才发现需要用他们提供的ListNode。
import java.util.*;

public class add_two_number {
    public static void main(String[] args) {
        List<Integer> l1 = new ArrayList<>() ;
        l1.add(2) ;
        l1.add(4) ;
        l1.add(1) ;
        l1.add(9) ;
        List<Integer> l2 = new ArrayList<>() ;
        l2.add(2);
        l2.add(0);
        l2.add(2);
        l2.add(1);
        System.out.println(addTwoList(l1 , l2));
    }

    private static List<Integer> numberToList(Integer num){
        String s = num.toString() ;
        char [] chars = s.toCharArray();
        List<Integer> list = new ArrayList<>() ;

        for (int i = 0 ; i < chars.length ; i ++){
            list.add(Integer.parseInt(String.valueOf(chars[i]))) ;
        }
        return list ;
    }

    private static Integer listToNumber(List<Integer> list){
        double num = 0 ;
        for (int i = list.size() - 1 ; i >= 0 ; i --){
            num += list.get(i) * Math.pow(10 , list.size() - 1 - i) ;
        }
        return Integer.valueOf((int) num);
    }

    private static List<Integer> addTwoList(List<Integer> l1 , List<Integer> l2){
        Integer num = listToNumber(l1) + listToNumber(l2) ;
        return numberToList(num) ;
    }


}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 第二次，使用了它提供的链表进行编码，在IDEA测试无误后，复制过去编译，几次编译都发现输出结果与预期结果不同，仔细一看题目才知要逆序，然后有了第三次。
public class add_two_numbers {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1) ;
        listNode.add(5);
        listNode.add(7);

        ListNode listNode1 = new ListNode(2) ;
        listNode1.add(3);
        listNode1.add(7);

        numberToList(listToNumber(listNode) + listToNumber(listNode1)).showList();
    }

    private static int listToNumber(ListNode l){
        int num = 0 ;
        ListNode temp = l ;
        int length = 0 ;
        while (temp.next != null){
            length += 1 ;
            temp = temp.next ;
        }
        temp = l ;
        length = length  ;
        while (length >= 0){
            num += temp.val * Math.pow(10 , length) ;
            temp = temp.next ;
            length -- ;
        }
        return num ;
    }

    private static ListNode numberToList(int num){
        ListNode listNode = new ListNode() ;
        ListNode temp = listNode ;
        String s = String.valueOf(num) ;
        char [] chars = s.toCharArray();
        for (int i = 0 ; i < chars.length ; i ++){

            temp.val = Character.getNumericValue(chars[i]);
            if (i == chars.length - 1){
                break;
            }
            temp.next = new ListNode();
            temp = temp.next ;
        }
        return listNode ;
    }

    private static class ListNode {             //简单功能的ListNode
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
        
        private void add(int num) {
            ListNode temp = this;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = new ListNode(num);
        }
        
        private void showList() {
            ListNode temp = this;
            while (true) {
                System.out.print(temp.val + "\t");
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            System.out.println();
        }

    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84

第三次终于在LeetCode提供的编译器里通过了，点击提交，解答错误，我的方法是将链表的值遍历成int类型，再相加转换成链表，它的测试用例是：

最后执行的输入：
[9]
[1,9,9,9,9,9,9,9,9,9]

  • 1
  • 2
  • 3

结果已超出int类型的数据范围。

public class add_two_numbers2 {

    public static void main(String[] args) {
        ListNode2 l1 = new ListNode2(7) ;
        l1.add(3);
        l1.add(2);

        ListNode2 l2 = new ListNode2(7) ;
        l2.add(5);
        l2.add(1);

        numberToList(listToNumber(l1) + listToNumber(l2)).showList();
    }
    private static int listToNumber(ListNode2 l) {
        int num = 0 ;
        ListNode2 temp = l ;
        int powNum = 0 ;
        while (temp != null){
            num += temp.val * Math.pow(10 , powNum) ;
            temp = temp.next ;
            powNum ++ ;
        }
        return num ;
    }

    private static ListNode2 numberToList(int num){

        ListNode2 listNode2 = new ListNode2() ;
        ListNode2 temp = listNode2 ;
        StringBuffer sb = new StringBuffer(String.valueOf(num)) ;
        sb = sb.reverse() ;
        int index = 0 ;
        while (index < sb.length()){
            temp.val = Character.getNumericValue(sb.charAt(index)) ;
            if (index == sb.length() - 1){
                break;
            }
                temp.next = new ListNode2() ;
                temp = temp.next ;
                index ++ ;
        }
        return listNode2 ;
    }

    private static class ListNode2 {
        int val;
        ListNode2 next;
        ListNode2() {
        }
        ListNode2(int val) {
            this.val = val;
        }
        ListNode2(int val, ListNode2 next) {
            this.val = val;
            this.next = next;
        }
        private void add(int num) {
            ListNode2 temp = this;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = new ListNode2(num);
        }

        private void showList() {
            ListNode2 temp = this;
            while (true) {
                System.out.print(temp.val + "\t");
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            System.out.println();
        }

    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78

第四次，将int类型换成了long，并使用了上次提交时给出的用例测试，出了正确结果，在次点击提交：解答错误
此次的测试用例是：

最后执行的输入：
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
[5,6,4]

  • 1
  • 2
  • 3
public class add_two_numbers2 {

    public static void main(String[] args) {
        ListNode2 l1 = new ListNode2(9) ;

        ListNode2 l2 = new ListNode2(1) ;
        l2.add(9);
        l2.add(9);
        l2.add(9);
        l2.add(9);
        l2.add(9);
        l2.add(9);
        l2.add(9);
        l2.add(9);
        l2.add(9);

        numberToList(listToNumber(l1) + listToNumber(l2)).showList();
    }
    private static ListNode numberToList(long num){
        ListNode listNode = new ListNode() ;
        ListNode temp = listNode ;
        StringBuffer sb = new StringBuffer(String.valueOf(num)) ;
        sb = sb.reverse() ;
        int index = 0 ;
        while (index < sb.length()){
            temp.val = Character.getNumericValue(sb.charAt(index)) ;
            if (index == sb.length() - 1){
                break;
            }
                temp.next = new ListNode() ;
                temp = temp.next ;
                index ++ ;
        }
        return listNode ;
    }

    private static long listToNumber(ListNode l) {
        long num = 0 ;
        ListNode temp = l ;
        long powNum = 0 ;
        while (temp != null){
            num += temp.val * Math.pow(10 , powNum) ;
            temp = temp.next ;
            powNum ++ ;
        }
        return num ;
    }

    private static class ListNode2 {
        int val;
        ListNode2 next;
        ListNode2() {
        }
        ListNode2(int val) {
            this.val = val;
        }
        ListNode2(int val, ListNode2 next) {
            this.val = val;
            this.next = next;
        }
        private void add(int num) {
            ListNode2 temp = this;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = new ListNode2(num);
        }

        private void showList() {
            ListNode2 temp = this;
            while (true) {
                System.out.print(temp.val + "\t");
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            System.out.println();
        }

    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82

？？？
人傻了，看来转换类型再相加再转回去的方法行不通了，只能另求他法。

最后终于通过了

在这里插入图片描述

  • 最后的方法是，将两个链表对应节点的值相加，存到另一张链表上，类似于小时候学多位数加减法那样，只是这里相加是从头开始加，相加值大于等于10的，取余，向后进一位，后面也如此计算，直到两个链表皆为空，且无需再往后进位。

附上代码：

public class add_two_numbers3 {


    public static void main(String[] args) {
        ListNode2 l1 = new ListNode2(9) ;

        ListNode2 l2 = new ListNode2(1) ;
        l2.add(9);
        l2.add(9);
        l2.add(9);
        l2.add(9);
        l2.add(9);

        addTwoList(l1 , l2).showList();
    }

    private static ListNode2 addTwoList(ListNode2 l1 , ListNode2 l2){
        ListNode2 newList = new ListNode2() ;
        ListNode2 temp1 = l1 ;
        ListNode2 temp2 = l2 ;
        ListNode2 newListTemp = newList ;
        ListNode2 ZeroNode = new ListNode2(0) ;
        int last = 0 ;
        while (true){
            if (temp1 == null){         //若该链表已空，将其指向前面已经定义好的，值为0的节点，避免后面相加出行空指针异常
                temp1 = ZeroNode ;
            }
            if (temp2 == null){
                temp2 = ZeroNode ;
            }

            newListTemp.val = (temp1.val + temp2.val + last) % 10 ;
            last = (temp1.val + temp2.val + last) / 10;
            temp1 = temp1.next ;
            temp2 = temp2.next ;
            if ((temp1 == null && temp2 == null) && last == 0){
                break;
            }
            newListTemp.next = new ListNode2() ;
            newListTemp = newListTemp.next ;
        }
        return newList ;
    }

    private static class ListNode2 {
        int val;
        ListNode2 next;
        ListNode2() {
        }
        ListNode2(int val) {
            this.val = val;
        }
        ListNode2(int val, ListNode2 next) {
            this.val = val;
            this.next = next;
        }
        private void add(int num) {
            ListNode2 temp = this;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = new ListNode2(num);
        }

        private void showList() {
            ListNode2 temp = this;
            while (true) {
                System.out.print(temp.val + "\t");
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            System.out.println();
        }

    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78

做这道题花了好长时间，主要就是前面几次实在太粗心了，连续几次都没看清题目要求，也是把我自己给气笑了。最后做的正确结果也是有了思路之后，在IDEA里debug了好久才修改到正确的。
感兴趣的话也可以点击题目描述里的LeetCode链接，试试手或者看看别人的解法。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/929184
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号