链接：https://leetcode-cn.com/problems/add-two-numbers/

解题思路

初始化：

  • 初始化变量 ListNode ret，作为返回的“和链表”头节点
  • 初始化变量 ListNode cur， 用来遍历“和链表”
  • 初始化变量 boolean isCarry， 用来标记 l1.val 与 l2.val 的和是否大于等于 10

算法流程：

  • 当 l1 != null && l2 != null 时，同时遍历 l1，l2 两个链表，构建“和链表”
  • 如果两个链表长度不一致，那么就会出现 l1 链表遍历完成 l2还未遍历结束； l2 链表遍历完成 l1还未遍历结束这两种情况：
    • 当 l1 != null 时，接着遍历 l1 构建我们的“和链表”
    • 当 l2 != null 时，接着遍历 l2 构建我们的“和链表”
  • 最后，我们需要留意 isCarry是否为真，如果为真，则代表最后还有进位，我们需要在“和链表”的尾部再添加一个值为 1 的节点

代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  13.         ListNode ret = null;
  14.         ListNode cur = null;
  15.         boolean isCarry = false;
  16.         while(l1 != null && l2 != null){
  17.             if(cur == null){
  18.                 if(l1.val + l2.val >= 10){
  19.                     isCarry = true;
  20.                 }else {
  21.                     isCarry = false;
  22.                 }
  23.                 ret = new ListNode((l1.val + l2.val) % 10);
  24.                 cur = ret;
  25.             }else {
  26.                 if(isCarry){
  27.                     if(l1.val + l2.val + 1 >= 10){
  28.                         isCarry = true;
  29.                     }else {
  30.                         isCarry = false;
  31.                     }
  32.                     cur.next = new ListNode((l1.val + l2.val + 1) % 10);
  33.                     cur = cur.next;
  34.                 }else {
  35.                     if(l1.val + l2.val >= 10){
  36.                         isCarry = true;
  37.                     }else {
  38.                         isCarry = false;
  39.                     }
  40.                     cur.next = new ListNode((l1.val + l2.val) % 10);
  41.                     cur = cur.next;
  42.                 }
  43.             }
  44.             l1 = l1.next;
  45.             l2 = l2.next;
  46.         }
  47.         while(l1 != null) {
  48.             if(isCarry){
  49.                 if(l1.val + 1 >= 10){
  50.                     isCarry = true;
  51.                 }else {
  52.                     isCarry = false;
  53.                 }
  54.                 cur.next = new ListNode((l1.val + 1) % 10);
  55.                 cur = cur.next;
  56.             }else {
  57.                 cur.next = new ListNode(l1.val);
  58.                 cur = cur.next;
  59.             }
  60.             l1 = l1.next;
  61.         }
  62.         while(l2 != null) {
  63.             if(isCarry){
  64.                 if(l2.val + 1 >= 10){
  65.                     isCarry = true;
  66.                 }else {
  67.                     isCarry = false;
  68.                 }
  69.                 cur.next = new ListNode((l2.val + 1) % 10);
  70.                 cur = cur.next;
  71.             }else {
  72.                 cur.next = new ListNode(l2.val);
  73.                 cur = cur.next;
  74.             }
  75.             l2 = l2.next;
  76.         }
  77.         if(isCarry){
  78.             cur.next = new ListNode(1);
  79.         }
  80.         return ret;
  81.     }
  82. }

复杂度分析

  • 时间复杂度：

我们只需要遍历 的长度即可，时间复杂度为

  • 空间复杂度：

因为我们仅使用了有限的几个变量，所以额外空间复杂度为