LeetCode每日一练（两数之和）

小鱼儿 2022-10-19 05:33 250阅读 0赞

题目如下：

> 给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。  
> 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

![在这里插入图片描述][20210709175600918.png]  
题目很好理解，就是给你两个链表，比如243和564，需要逆序得到链表所代表的的数值，分别是342和465，将这两个数相加，得到结果807，再逆序存回一个链表并返回。

了解题目的意思之后，我们先来分析一下，这道题思路还是比较简单的，首先遍历两个链表，并对遍历结果进行逆序处理，得到两个数，然后相加得到结果，再逆序存入链表。

首先我们需要得到两个链表所代表的数值：

运行结果：

342+465=807

得到结果之后，就创建一个新的链表，将结果逆序放入新链表中：

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
            // 遍历l1链表得到数值
            StringBuilder sb = new StringBuilder();
            while (l1 != null) { 
                sb.append(l1.val);
                l1 = l1.next;
            }
            // 将数值逆序
            String str1 = sb.reverse().toString();
            Integer num1 = Integer.valueOf(str1);
    
            // 清空sb
            sb.setLength(0);
    
            // 以同样的方式得到链表l2的数值
            while (l2 != null) { 
                sb.append(l2.val);
                l2 = l2.next;
            }
            String str2 = sb.reverse().toString();
            Integer num2 = Integer.valueOf(str2);
    
            // 两数相加
            int result = num1 + num2;
            // 将结果整理成链表
            String strResult = String.valueOf(result);
            char[] chars = strResult.toCharArray();
            ListNode listNode = new ListNode();
            ListNode temp = listNode;
            for (int i = chars.length - 1; i >= 0; --i) { 
                if (i == 0) { 
                    temp.val = Integer.parseInt(String.valueOf(chars[i]));
                    // 对于尾结点，其指针域为空
                    temp.next = null;
                } else { 
                    temp.val = Integer.parseInt(String.valueOf(chars[i]));
                    temp.next = new ListNode();
                    temp = temp.next;
                }
            }
            return listNode;
        }

都是一些非常简单的链表操作，如果还不会链表的话，数据结构需要补补课了呦，遍历返回的链表就得到结果：

708

怀着喜悦的心情将代码放到LeetCode上运行，结果没通过：  
![在这里插入图片描述][20210709180744888.png]  
原来是测试数据太大了，导致int类型装不下，那就将其改为long类型：

......
    Long num1 = Long.valueOf(str1);
    Long num2 = Long.valueOf(str2);
    Long result = num1 + num2;
    ......

结果还是没有通过：  
![在这里插入图片描述][20210709180946868.png]  
我的天，测试数据居然这么长，那没办法，我们将其改为BigDecimal就可以了，最终代码：

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
            // 遍历l1链表得到数值
            StringBuilder sb = new StringBuilder();
            while (l1 != null) { 
                sb.append(l1.val);
                l1 = l1.next;
            }
            // 将数值逆序
            String str1 = sb.reverse().toString();
            BigDecimal decimal1 = new BigDecimal(str1);
    
            // 清空sb
            sb.setLength(0);
    
            // 以同样的方式得到链表l2的数值
            while (l2 != null) { 
                sb.append(l2.val);
                l2 = l2.next;
            }
            String str2 = sb.reverse().toString();
            BigDecimal decimal2 = new BigDecimal(str2);
    
    
            // 两数相加
            BigDecimal resultDecimal = decimal1.add(decimal2);
            // 将结果整理成链表
            String strResult = resultDecimal.toString();
            char[] chars = strResult.toCharArray();
            ListNode listNode = new ListNode();
            ListNode temp = listNode;
            for (int i = chars.length - 1; i >= 0; --i) { 
                if (i == 0) { 
                    temp.val = Integer.parseInt(String.valueOf(chars[i]));
                    temp.next = null;
                } else { 
                    temp.val = Integer.parseInt(String.valueOf(chars[i]));
                    temp.next = new ListNode();
                    temp = temp.next;
                }
            }
            return listNode;
        }

测试通过：  
![在这里插入图片描述][20210709181131313.png]  
可以看到执行用时是比较长的，只击败了18.79%的用户，我们来分析一下导致执行用时过长的原因，首先是对链表的遍历，我们一共遍历了两次链表，然后是链表的创建，这些都是非常耗时的操作，有没有办法能够只进行一次遍历就完成题目的要求呢？

题目表示链表的数字是按逆序方式存储的，这刚好给了我们一个便利的处理方式，我们可以同时遍历两个链表，并分别取出两个链表同一位置上的两个数值，相加后直接放到新创建的链表中，比如243和564链表：

![在这里插入图片描述][20210709182946864.png]  
由于数值是逆序存储，所以链表的第一个元素其实是数值的最后一个数，将2和5相加得到7，故结果的最后一位数为7，再将其存入新的链表，作为第一个结点即可：  
![在这里插入图片描述][20210709183133214.png]  
然后l1和l2后移一位：  
![在这里插入图片描述][2021070918321992.png]  
该位置上的两个数相加结果为10，这里就需要考虑到进位的问题，要让当前位置的数值为0，并向前一位进1，只需让相加的结果除以10，就能够得到进位；比如10除以10等于1，就向前进1，23除以10等于2，就向前进2。再让相加的结果模10就能够得到当前位置的结果数，比如10模10等于0，当前位置就是0，23模10等于3，当前位置就是3。由此可知，结果的倒数第二个数为0，将其存入新的链表：  
![在这里插入图片描述][20210709183539789.png]  
l1、l2继续后移：  
![在这里插入图片描述][20210709183610884.png]  
该位置上的两个数相加等于7，需要注意还得加上进位，所以结果的第一位为8，存入新链表：  
![在这里插入图片描述][20210709183724369.png]  
此时l1、l2后移，结果为空，故计算结束，这样我们就通过一次遍历直接得到了结果链表。

当然，我们还需要考虑两个链表不一样长的情况，比如：  
![在这里插入图片描述][20210709183857136.png]  
对于这种情况，前面两个数的求法都是一样的，5加2等于7，存入新链表，6加4等于10，向前进1，将0存入新链表，此时l1、l2再后移，l1为空，但l2仍然有值，这时候我们给l1一个占位，让其等于0，这样就能够继续相加，此时4加0，再加上进位等于5，所以最终结果为：  
![在这里插入图片描述][2021070918410442.png]  
由此得到代码：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
            // 新链表的头指针、尾指针均初始化为null
            ListNode head = null, tail = null;
            // 初始化进位为0
            int carry = 0;
            // 同时遍历l1和l2链表
            while (l1 != null || l2 != null) { 
                // 处理两个链表不等长的情况，若某个链表遍历结束，结点为null，则让其值等于0
                int n1 = l1 != null ? l1.val : 0;
                int n2 = l2 != null ? l2.val : 0;
                // 两数相加，记得加上进位
                int sum = n1 + n2 + carry;
                // 采用尾插法建立新链表
                if (head == null) { 
                    head = tail = new ListNode(sum % 10); // 模10得到当前位置的数值
                } else { 
                    tail.next = new ListNode(sum % 10); // 模10得到当前位置的数值
                    tail = tail.next;
                }
    
                // 计算进位
                carry = sum / 10;
                if (l1 != null) { 
                    l1 = l1.next;
                }
                if (l2 != null) { 
                    l2 = l2.next;
                }
            }
            // 若是两个链表遍历结束后，仍然有进位，则进位应成为新的一位
            if (carry > 0) { 
                tail.next = new ListNode(carry);
            }
            return head;
        }

因为计算得到的结果需要按顺序依次放入新链表，故而这里采用尾插法建立新的链表。

最后将代码提交到LeetCode上，测试通过：  
![在这里插入图片描述][20210709184836446.png]

[20210709175600918.png]: /images/20221005/7677781fa11f49de82f9e526f7ab4d48.png
[20210709180744888.png]: /images/20221005/7532d85d2b334c7d8c05674fcf65e8e0.png
[20210709180946868.png]: /images/20221005/df2097af38cf4a70b766dd10c030aa7f.png
[20210709181131313.png]: /images/20221005/d10b0793bd1345e0898a35a0c6ec0f93.png
[20210709182946864.png]: /images/20221005/b8a63e568f6840cb94600f94cfb69576.png
[20210709183133214.png]: /images/20221005/b27433f56dc34cc7a4905582fe809cc1.png
[2021070918321992.png]: /images/20221005/3a964d9c71594260afeb684af726f2f3.png
[20210709183539789.png]: /images/20221005/94bab81960974534ae671976bcd54766.png
[20210709183610884.png]: /images/20221005/cc12225981d141189e7a403da733f938.png
[20210709183724369.png]: /images/20221005/d93a128f232340bc897ff7ebf6d9f840.png
[20210709183857136.png]: /images/20221005/87f258e4210c4f8ca025d82c0f1a0bac.png
[2021070918410442.png]: /images/20221005/4007e471ed084d1191f24f1c625422f2.png
[20210709184836446.png]: /images/20221005/779aa3800f6a40b4834f048774883dda.png