内容简介:给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外,这两个数都不会以 0 开头。 示例:
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。 示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807
数据结构
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { } } 复制代码
解题思路
分解问题:
- 如果两个数都为0:
// 0+任何数都等于任何数 if(l1.val == 0 && l1.next == null) { return l2; } if(l2.val == 0 && l2.next == null) { return l1; } 复制代码
- 如果l1或l2为个位数:
// l1是个位数 if(l1.next == null) { if(l1.val + l2.val >= 10) { l1.val = (l1.val + l2.val) % 10; l1.next = addTwoNumbers(new ListNode(1), l2.next); return l1; } else { l1.val += l2.val; l1.next = l2.next; return l1; } } // l2是个位数 if(l2.next == null) { if(l1.val + l2.val >= 10) { l1.val = (l1.val + l2.val) % 10; l1.next = addTwoNumbers(l1.next, new ListNode(1)); return l1; } else { l1.val +=l2.val; return l1; } } 复制代码
- 当特殊条件都分析完成之后,就剩下了l1和l2均是2位数以上的情况,那么他们的个位数经过计算后,剩下的位数依然可以按照上面的条件进行就算了,也就是使用递归
// l1和l2都不是个位数 if(l1.val + l2.val >= 10) { l1.val = (l1.val + l2.val) % 10; l1.next = addTwoNumbers(l1.next, new ListNode(1)); l1.next = addTwoNumbers(l1.next, l2.next); } else { l1.val += l2.val; l1.next = addTwoNumbers(l1.next, l2.next); } return l1; 复制代码
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
数据结构与算法JavaScript描述
[美] Michael McMillan / 王群锋、杜 欢 / 人民邮电出版社 / 2014-8 / 49.00元
通过本书的学习,读者将能自如地选择最合适的数据结构与算法,并在JavaScript开发中懂得权衡使用。此外,本书也概述了与数据结构与算法相关的JavaScript特性。 本书主要内容如下。 数组和列表:最常用的数据结构。 栈和队列:与列表类似但更复杂的数据结构。 链表:如何通过它们克服数组的不足。 字典:将数据以键-值对的形式存储。 散列:适用于快速查找和检索。......一起来看看 《数据结构与算法JavaScript描述》 这本书的介绍吧!