LeetCode题解-AddTwoNumbers

男娘i 2022-05-23 12:30 225阅读 0赞

# LeetCode题解-AddTwoNumbers #

## 问题描述 ##

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.

## 思路分析 ##

这个问题其实就是同时遍历两个列表依次相加，可以分为四种情况是：

*  基本情况：两个列表指针的指向都有数字
 *  指向列表`l1`的指针走到了最末尾
 *  指向列表`l2`的指针走到了最末尾
 *  两个列表的指针指向都已经为空

其中第2，3，4中情况需要特殊处理

还有需要注意的是：两个数字相加大于10的情况，后面的结果需要加上1（这个可以通过设置一个旗帜变量解决）

## 代码实现 ##

C++版本

// ListNode的定义
    struct ListNode {
        int val;
        ListNode *next;
    
        ListNode(int x) : val(x), next(nullptr) {}
    };
    
    // 通过给定的数据创建一个ListNode列表
    ListNode *createList(vector<int> &nums) {
        ListNode *head = new ListNode(0);
        ListNode *current = head;
        for (auto iter = nums.begin(); iter != nums.end();) {
            current->val = *iter;
            if (++iter != nums.end())
                current->next = new ListNode(0);
            else
                current->next = nullptr;  // 如果是最后一个数据了，则next指向为NULL
            current = current->next;
        }
        return head;
    }
    
    
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode *p1 = l1;
        ListNode *p2 = l2;
    
        ListNode *head = new ListNode(0);
        ListNode *current = head;
        int sum = 0;
        int flag = 0;
    
        while (p1 || p2 || flag) {
            sum = (p1 ? p1->val : 0) + (p2 ? p2->val : 0);
    
            if (flag == 1) {
                sum += 1;
                flag = 0;
            }
            if (sum >= 10) {
                sum %= 10;
                flag = 1;
            }
            current->val = sum;
    
            p1 = p1 ? p1->next : p1;
            p2 = p2 ? p2->next : p2;
            if (p1 || p2 || flag)
                current->next = new ListNode(0);
            else
                current->next = nullptr;
            current = current->next;
        }
        return head;
    }
    
    int main() {
        vector<int> v1 = {
       5};
        vector<int> v2 = {
       5};
        ListNode *l1 = createList(v1);
        ListNode *l2 = createList(v2);
        ListNode *ls = addTwoNumbers(l1, l2);
        while (ls) {
            cout << ls->val << ' ';
            ls = ls->next;
        }
        cout << endl;
        return 0;
    }

Scala版本

感觉函数式编程语言真的有时候很简洁，让编程完全换了一种思路

下面Scala版本的实现没有采用LeetCode定义的`ListNode`结构，而是直接使用Scala本身提供的`List`实现的

通过使用模式匹配，分列出来可能出现的四种情况，然后通过递归依次遍历两个列表，将每次计算的结果放在前面

体验一下函数式编程的简介之处吧！

package leetcode
    
    object AddTwoNumbers {
    
      def addTwoNumbers(l1: List[Int], l2: List[Int]): List[Int] = {
    
        def addWithCarry(lists: (List[Int], List[Int]), carry: Int) = lists match {
          case (Nil, Nil) => if (carry == 0) Nil else List(carry)
          case (x :: xtail, Nil) => addHeads(x, 0, carry, (xtail, Nil))
          case (Nil, y :: ytail) => addHeads(0, y, carry, (Nil, ytail))
          case (x :: xtail, y :: ytail) => addHeads(x, y, carry, (xtail, ytail))
        }
    
        def addHeads(x: Int, y: Int, carry: Int, tails: (List[Int], List[Int])): List[Int] = {
          val sum = x + y + carry
          // 每次的计算结果放在前面，后面采用递归依次计算
          sum % 10 :: addWithCarry(tails, sum / 10)
        }
    
        addWithCarry((l1, l2), 0)
      }
    
    
      def main(args: Array[String]): Unit = {
        val l1 = List(2, 4, 3)
        val l2 = List(5, 6, 4)
        val ls = addTwoNumbers(l1, l2)
        ls.foreach(print(_))
      }
    
    }