1. 题目

两数相加

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

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

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

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

2. 解题思路

初始化新链表的头节点为哑结点。

while循环2个链表，对应的数字相加，引入进位的概念，如果相加>9，则进位1，进位带入下一步的运算。如果其中一个链表的节点为空，计算时以0代替。

2个链表循环结束后，哑结点的下一个节点则为目的链表的头节点。

3. 题解

  1. // 链表节点类
  2. public class ListNode {
  4.     public int value;
  5.     public ListNode next;
  7.     public ListNode(int x) {
  8.         value = x;
  9.     }
  10. }
  1. public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  3.     //初始化一个哑结点
  4.     ListNode dummyNode = new ListNode(0);
  5.     //设置指针进行移动
  6.     ListNode curr = dummyNode;
  8.     //定义进位
  9.     int carry = 0;
  11.     //同时循环2个链表
  12.     while(l1.next != null || l2.next != null) {
  13.         int value1 = l1 != null ? l1.value : 0;
  14.         int value2 = l2 != null ? l2.value : 0;
  15.         int sum = carry + value1 + value2;
  17.         //判断进位
  18.         carry = sum / 10;
  19.         curr.next = new ListNode(sum % 10);
  21.         //往后移动
  22.         curr = curr.next;
  24.         if(l1 != null) {
  25.             l1 = l1.next;
  26.         }
  28.         if(l2 != null) {
  29.             l2 = l2.next;
  30.         }
  31.     }
  33.     //循环出来后进位如果是1，需要再向后延展一位1
  34.     if(carry > 0) {
  35.         curr.next = new ListNode(1);
  36.     }
  38.     return dummyNode.next;
  39. }

4. 分析

时间复杂度

O(max(m, n))

空间复杂度

O(max(m, n))

5. 知识点

链表

哑结点