编辑
2022-11-09
数据结构与算法
0
请注意,本文编写于 555 天前,最后修改于 246 天前,其中某些信息可能已经过时。

目录

题目
理解题意
解题思路
解法

题目

​ 给出两个非空链表用来表示两个非负整数,其中他们各自的位数是按照逆序的方式存储的,并且他们的每个节点只能存储一位数字。如果我们将这两个数相加起来,则会返回一个新的链表来表示他们的和,您可以假设除了数字0之外,这两个数字不会以0开头。

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出:7 -> 0 -> 8

原因:342 + 465 = 807

理解题意

​ 1、一个链表表示一个整数

​ 2、每个节点存储一个数字

​ 3、各自的位数逆序存储

​ 4、链表相加,即链表表示的整数相加

​ 5、返回链表表示的两数之和

解题思路

​ 解法一:分别将链表转成数字,再相加

​ 解法二:直接将对应位置数字相加

解法

暴力解法(不推荐)

​ 1、遍历两个链表使用数学思维分别将他们转成整数

​ 2、对两个整数进行求和得到sum

​ 3、将sum按照数学思维再转换成链表

边界问题

​ 链表转整数时,next==null结尾

​ 整数转链表,处理完最高位时,value==0

​ 可能存在数值溢出问题

对应位置数字相加

​ 1、时间复杂度只有O(max(m,n))

​ 2、不存在数值溢出的问题

java
public class TwoLinkedListSum { public static void main(String[] args) { ListNode l1 = new ListNode(5); ListNode l11 = new ListNode(6); ListNode l12 = new ListNode(3); l1.next = l11; l11.next = l12; ListNode l2 = new ListNode(5); ListNode l21 = new ListNode(6); ListNode l22 = new ListNode(3); l2.next = l21; l21.next = l22; ListNode listNode = addTwoNumbers(l1, l2); ListNode tmp = listNode; while (tmp != null) { System.out.print(tmp.val); tmp = tmp.next; } // 037 } private static ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode p = l1, q = l2; ListNode resultHead = new ListNode(-1); ListNode cur = resultHead; int carry = 0; // 进位 // 1、遍历两个链表 while (p != null || q != null) { // 以长链表为准 int x = p != null ? p.val : 0; int y = q != null ? q.val : 0; // 2、对应位置的节点数值相加 int sum = x + y + carry; carry = sum / 10; sum = sum % 10; // 3、将计算结果插入新链表尾部 cur.next = new ListNode(sum); cur = cur.next; p = p == null ? p : p.next; q = q == null ? q : q.next; } // 处理进位 if (carry > 0) { cur.next = new ListNode(carry); } return resultHead.next; } static class ListNode { int val; ListNode next; ListNode() {}; ListNode(int x) { val = x; } } }

本文作者:whitebear

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!