我是靠谱客的博主 年轻鱼,这篇文章主要介绍链表求和(尾插法)链表求和,现在分享给大家,希望可以做个参考。

链表求和

题目描述

给定两个用链表表示的整数,每个节点包含一个数位。

这些数位是反向存放的,也就是个位排在链表首部。

编写函数对这两个整数求和,并用链表形式返回结果。
输入:(7 -> 1 -> 6) + (5 -> 9 -> 2),即617 + 295
输出:2 -> 1 -> 9,即912

题解(java)

复制代码
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
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { //虚拟头节点(哑结点) ListNode dummy = new ListNode(0); ListNode temp = dummy; //进位 int carry = 0; while(l1!=null || l2!=null || carry>0){ int i = l1==null? 0 : l1.val; int j = l2==null? 0 : l2.val; //相加之和(包含进位的) int sum = i + j +carry; if(sum>=10){ //尾插法连接 temp.next = new ListNode(sum%10); }else{ temp.next = new ListNode(sum); } //更新进位的值 carry = sum / 10; temp = temp.next; if(l1!=null){ l1 = l1.next; } if(l2!=null){ l2 = l2.next; } } return dummy.next; } }

图示

在这里插入图片描述

详解(尾插法连接)

  • 1>.简单来说,该题需要四个变量,一个是 l1 节点的值 i,一个是 l2 节点的值 j,一个是进位数 count,一个是计算总和的值,其中进位数初始化为0。
  • 2>.当 i,j,count中只要有一个不为 null 或 0时,都需要进入遍历,产生新的节点用头插法连接到链表中去
  • 3>.其中进位数 count = sum/10,新的节点的值分为两种情况:【1).当sum<10时,temp.next == sum,当 sum >= 10时,需要对sum进行取余,即temp.next == sum%10】
  • 最后返回新的节点

进阶

进阶:思考一下,假设这些数位是正向存放的,又该如何解决呢?

示例:

输入:(6 -> 1 -> 7) + (2 -> 9 -> 5),即617 + 295
输出:9 -> 1 -> 2,即912

  • 这里先把原来的两个链表反转,再采用头插法连接即可

声明

  • 原作者:E.L.E
  • <本文章著作权归作者所有,商业转载请获得作者授权,非商业转载请注明出处>
  • <欢迎大家评论>

最后

以上就是年轻鱼最近收集整理的关于链表求和(尾插法)链表求和的全部内容,更多相关链表求和(尾插法)链表求和内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(59)

评论列表共有 0 条评论

立即
投稿
返回
顶部