题目

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

示例 1：

image.png

  1. 输入：l1 = [2,4,3], l2 = [5,6,4]
  2. 输出：[7,0,8]
  3. 解释：342 + 465 = 807.

示例 2：

  1. 输入：l1 = [0], l2 = [0]
  2. 输出：[0]

示例 3：

  1. 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
  2. 输出：[8,9,9,9,0,0,0,1]

思路与算法

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。
我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2，进位值为carry，则它们的和为 n1+n2+carry；其中，答案链表处相应位置的数字为 (n1+n2+carry)mod10，而新的进位值为image.png。
如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0 。
此外，如果链表遍历结束后，有 carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry。

代码

  1. public class ListNode {
  3.     public int value;
  5.     /**
  6.      * 下一个链表对象
  7.      */
  8.     public ListNode next;
  10.     /**
  11.      * 赋值链表的值
  12.      * @param value 值
  13.      */
  14.     public ListNode(int value) {
  15.         this.value = value;
  16.     }
  18. }
  20. public class TwoNumAdd {
  22.     /**
  23.      * create by: Chen Bei Jin
  24.      * description: TODO
  25.      * create time: 2021/8/12 9:18
  26.      * @param listNodeOne 链表1
  27.      * @param listNodeTwo 链表2
  28.      * @return 结果
  29.      */
  30.     public static ListNode addTwoNumbers(ListNode listNodeOne, ListNode listNodeTwo) {
  31.         // 头节点
  32.         ListNode head = null;
  33.         // 尾节点
  34.         ListNode tail = null;
  35.         // 数值为10向前加1
  36.         int carry = 0;
  37.         // 判断链表是否为空
  38.         while (listNodeOne != null || listNodeTwo != null) {
  39.             // 获取值
  40.             int oneNum = listNodeOne != null ? listNodeOne.value : 0;
  41.             int twoNum = listNodeTwo != null ? listNodeTwo.value : 0;
  42.             int sum = oneNum + twoNum + carry;
  43.             // 判断结果链头是否为空
  44.             if (head == null) {
  45.                 // 初始化 创建链头和链尾
  46.                 head = tail = new ListNode(sum % 10);
  47.                 // 否则 就修改链尾
  48.             } else {
  49.                 // 指向下一个节点
  50.                 tail.next = new ListNode(sum % 10);
  51.                 // 当前节点是 下一个节点
  52.                 tail = tail.next;
  53.             }
  54.             // 获取10的倍数 取整 11/10 = 1.111 因为是int类型 所有 等于 1
  55.             carry = sum / 10;
  56.             // 两个链表向后移动
  57.             if (listNodeOne != null) {
  58.                 listNodeOne = listNodeOne.next;
  59.             }
  60.             if (listNodeTwo != null) {
  61.                 listNodeTwo = listNodeTwo.next;
  62.             }
  63.         }
  65.         // 判断最后一个数还有没有要向前加1
  66.         if (carry > 0) {
  67.             tail.next = new ListNode(carry);
  68.         }
  69.         return head;
  70.     }
  72.     public static void main(String[] args) {
  73.         ListNode listNodeOne = new ListNode(3);
  74.         listNodeOne.next = new ListNode(4);
  75.         listNodeOne.next.next = new ListNode(2);
  76.         ListNode listNodeTwo = new ListNode(4);
  77.         listNodeTwo.next = new ListNode(6);
  78.         listNodeTwo.next.next = new ListNode(5);
  80.         ListNode listNode = addTwoNumbers(listNodeOne, listNodeTwo);
  81.         while (listNode != null) {
  82.             System.out.println(listNode.value);
  83.             if (listNode != null) {
  84.                 listNode = listNode.next;
  85.             }
  86.         }
  87.     }
  88. }

复杂度分析

  1. 时间复杂度：O(max⁡(m,n))，其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。<br />    空间复杂度：O(1)。注意返回值不计入空间复杂度。

转载：https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode-solution/