title: 算法小练——两数相加
categories:

  • Algorithms
    tags:
  • medium
    abbrlink: 1282388112
    date: 2019-11-03 17:13:36

描述

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

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

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

示例

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

代码

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      if((l1.val+l2.val)>=10){
                if(l1.next==null && l2.next==null){
                    l1.next =new ListNode(0);
                }else if(l1.next==null){
                    ListNode cur;
                    cur =l1;
                    l1 = l2;
                    l2 = cur;
                }
                l1.next.val = l1.next.val+1;
            }
            ListNode newListNode = new ListNode((l1.val+l2.val)>=10?l1.val+l2.val-10:l1.val+l2.val);

            ListNode temp = newListNode;
            while(l1.next!=null || l2.next!=null){
                l1 = l1.next;
                l2 = l2.next;
                if(l2==null){
                    l2 =new ListNode(0);
                }else if(l1 ==null){
                    l1=new ListNode(0);
                }
                if((l1.val+l2.val)>=10){
                    if(l1.next==null && l2.next==null){
                        l1.next =new ListNode(0);
                    }else if(l1.next==null){
                        ListNode cur;
                        cur =l1;
                        l1 = l2;
                        l2 = cur;
                    }
                    l1.next.val = l1.next.val+1;
                }
                ListNode newListNode2 = new ListNode((l1.val+l2.val)>=10?l1.val+l2.val-10:l1.val+l2.val);

                while (temp.next!=null){
                    temp =temp.next;
                }
                temp.next =newListNode2;
            }
            return newListNode;
        }
}

笔记

这道题，对于初入算法的我来说有些难度。最开始，就通过唯一的例子来思考正常运算的逻辑。主要难点在于，首先要判断是否满10进1，同时，进1的情况要发生在node.next存在的时候，不存在还需要new一个 值为0的节点。