笔试题-求两数之和

• 题目

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

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

• 编码解答（递归实现）

package com.dairuijie.consumer.web.learn;
/*** <p>给出两个 <strong>非空strong> 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 <strong>逆序strong> 的方式存储的，并且它们的每个节点只能存储 <strong>一位strong> 数字。p><p>如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。p><p>您可以假设除了数字 0 之外，这两个数都不会以 0 开头。p><p><strong>示例：strong>p><pre><strong>输入：strong>(2 -> 4 -> 3) + (5 -> 6 -> 4)
<strong>输出：strong>7 -> 0 -> 8
<strong>原因：strong>342 + 465 = 807
pre>
<div><div>Related Topicsdiv><div><li>链表li><li>数学li>div>div>\n<div><li>👍 5291li><li>👎 0li>div>* @Title:  Solution.java   * @Package com.zhonglian.ctx.consumer.web.learn   * @Description:    描述   * @author: drj     * @date:   2020年11月27日 下午1:48:33   * @version V1.0 * @Copyright:*/
public class Solution {public static void main(String[] args) {ListNode nodeOne = new ListNode(2);nodeOne.next = new ListNode(4);nodeOne.next.next = new ListNode(9);//nodeOne.next.next.next = new ListNode(9);/*nodeOne.next.next.next.next = new ListNode(9);nodeOne.next.next.next.next.next = new ListNode(9);nodeOne.next.next.next.next.next.next = new ListNode(9);*/ListNode nodeTwo = new ListNode(5);nodeTwo.next = new ListNode(6);nodeTwo.next.next = new ListNode(4);nodeTwo.next.next.next = new ListNode(9);ListNode sum = new ListNode(0);ListNode result =sum;//System.err.println(addTwoNumbers(nodeOne, nodeOne));System.err.println(add(nodeOne, nodeTwo, sum,result));}/*** * @Title: add   * @Description: TODO(描述这个方法的作用)   * @param: @param nodeOne 非空链表1* @param: @param nodeTwo 非空链表2* @param: @param tempNode 每次递归使用临时链表* @param: @param resultNode 最终存放结果node* @param: @return      * @return: ListNode   * @author: Drj   * @throws*/public static ListNode add(ListNode nodeOne, ListNode nodeTwo,ListNode tempNode,ListNode resultNode) {/*** 两个链表长度不一定相等* 所以需要判断其中一个已经没有next 节点 当没有next 节点的时候 手动设置一个值为0 的节点*/if(nodeOne == null) {nodeOne = new ListNode(0);}if(nodeTwo ==null) {nodeTwo = new ListNode(0);}int oneValue = nodeOne.val;int twoValue = nodeTwo.val;/*** 根据要求加两个数的和* 1、当和没有超过两位数直接赋值给临时节点。* 2、和超过两位数需要考虑进位问题。eg nodeOne 9、9、 9 nodeTwo 9,9,9* 18 18 18 按照规则就是 最后一位是8 一进位 就是 19 然后 倒数第二个就是9 继续进位 19 倒数第三位就是 9 倒数第四位就是1  综合下来就是8991* 由于是 逆序 在重新逆序后就是1998* 3、考虑位数不等的情况 eg nodeOne:9、9  nodeTwo: 9、9、9* 也就是开始注释写的没有节点后需要我们手动加一个 也可以直接设置为0  节约内存*/int sumValue = oneValue + twoValue;if(sumValue >= 10) {int carry = sumValue / 10;int y = sumValue % 10;if(nodeOne.next == null && nodeTwo.next == null) {//两个链表都是最后一位不需要考虑进位直接追加到新的链表即可tempNode.next = new ListNode(y);tempNode.next.next = new ListNode(carry);tempNode = tempNode.next;}else{tempNode.next = new ListNode(y);// 进位的话需要考虑 两个数组是否有一个已经没有下一个节点了  要将进位的1 加到有next 节点的链表中if(nodeOne.next != null) {nodeOne.next.val = nodeOne.next.val + carry;}else {nodeTwo.next.val = nodeTwo.next.val + carry;}}}else {tempNode.next = new ListNode(sumValue);}/*** 当两个链表中都没有next 节点说明都计算完了 所以就可以跳出递归返回最终结果*/if(nodeOne.next == null && nodeTwo.next == null) {return resultNode.next;}return add(nodeOne.next, nodeTwo.next, tempNode.next,resultNode);}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！