categories: leetcode

2.png

题目描述

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.

参考代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. class Solution {
  10.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  11.         if(l1 == null) {
  12.             l1 = new ListNode(0);
  13.         }
  14.         if(l2 == null) {
  15.             l2 = new ListNode(0);
  16.         }
  18.         if(l1.next == null && l2.next == null) {//基准情况
  19.             int val = l1.val + l2.val;
  20.             if(val > 9) {
  21.                 ListNode node = new ListNode(val%10);
  22.                 node.next = new ListNode(1);//最大的数字也只能是19
  23.                 return node;
  24.             }
  25.             else {
  26.                 return new ListNode(val);
  27.             }
  28.         }
  29.         else {
  30.             int val = l1.val + l2.val;
  31.             if(val > 9) {
  32.                 val -= 10;
  33.                 if(l1.next != null) {//将进位赋值其一
  34.                     l1.next.val++;
  35.                 }
  36.                 else if(l2.next != null) {
  37.                     l2.next.val++;
  38.                 }
  39.             }
  40.             ListNode node = new ListNode(val);
  41.             node.next = addTwoNumbers(l1.next,l2.next);
  42.             //最终返回的结果
  43.             return node;
  44.          }
  45.     }
  46. }

思路及总结

涉及到链表和递归，感觉自己的基础实在是太差了，基础的算法思想都不会使用，还有就是自己的java基础也很薄弱，经常不知道如何来调用一些常用函数，结合自身情况，尽早提升吧。
本题主要要考虑到进位的安排，使用了递归，递归问题一般都能转换为循环问题，如https://www.programcreek.com/2012/12/add-two-numbers/，复杂度为O(n)，进位只会进1。

参考

https://blog.csdn.net/yanyumin52/article/details/79811375
https://blog.csdn.net/w496272885/article/details/80212426