2019-05-20 | 算法 | UNLOCK

两数相加

扯点别的

今天是520呀,我竟然在写代码,我的天,忍不了…..算了,还是忍忍吧,分享张图片,平复平复我的小心脏,哇呀呀,好恶心~



一句话结束这个话题 : 自律的人是最美的,自律绝不是嘴上说说滴~加油💪(ง •_•)ง

题目描述

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

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

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

示例:

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

思路提供

OK,说下思路,题目意思可以简化为 : 给定两个非空链表,需求是将每个链表节点对应的数据域的元素相加即可,所以这是不是相当于传统的对两个整数相加的plus版本呢,哈哈.无非注意一点就是 :

  • 本题是对链表的操作,即将两个链表对应节点数据加和存入另一个链表的对应节点
  • 注意链表对应数据相加时的进位

以下给出C++和JavaScript两种解法,但是思路都一样,所以请读者自行选择适合自己的语言.🤭

Talk is cheap,show you my code

  • C++解法

      class Solution {
      public:
          ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
              ListNode *dummy = new ListNode(-1), *cur = dummy;
              int carry = 0;
              while (l1 || l2) {
                  int val1 = l1 ? l1->val : 0;
                  int val2 = l2 ? l2->val : 0;
                  int sum = val1 + val2 + carry;
                  carry = sum / 10;
                  cur->next = new ListNode(sum % 10);
                  cur = cur->next;
                  if (l1) l1 = l1->next;
                  if (l2) l2 = l2->next;
              }
              if (carry) cur->next = new ListNode(1);
              return dummy->next;
          }
      };
    
  • Javascript解法

      var addTwoNumbers = function(l1, l2) {
        let root = {};
        let carry = 0;
        let cursor = root;
    
        while( l1 || l2 ) {
          let sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + carry;
          cursor.next = {
            val: sum % 10
          }
          cursor = cursor.next;
          carry = sum>9 ? 1 : 0;
          l1 = l1 && l1.next;
          l2 = l2 && l2.next;
        }
        if ( carry > 0 ) {
          cursor.next = {
            val: carry
          }
        }
    
        return root.next;
      };    
    

评论加载中