本文共 2911 字，大约阅读时间需要 9 分钟。

2. 两数相加

难度中等

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

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

（1）设置两根指针分别指向两链表头，以相同的速度向后遍历

思路1.0：

创建新链表作为结果链表，额外的空间成本

代码1.0：

将结果存在了新建的一个节点上

class Solution {
   public:    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
           ListNode* cur1 = l1;        ListNode* cur2 = l2;        ListNode* ans = new ListNode(-1);        ListNode* curAns = ans;        bool isCarry = false;        while (cur1 != NULL || cur2 != NULL) {
               int val1;            int val2;            if (cur1 == NULL) {
                   val1 = 0;            }            else {
                   val1 = cur1->val;                cur1 = cur1->next;            }            if (cur2 == NULL) {
                   val2 = 0;            }            else {
                   val2 = cur2->val;                cur2 = cur2->next;            }            int total = val1 + val2 + isCarry;            if (total >= 10) {
                   total -= 10;                isCarry = true;            }            else {
                   isCarry = false;            }            ListNode* newNode = new ListNode(total);            curAns->next = newNode;            curAns = curAns->next;        }        if (isCarry) {
               ListNode* newNode = new ListNode(1);            curAns->next = newNode;        }        return ans->next;    }};

思路2.0：

选择在原来的其中一条较长链表作为结果链表，以节省空间开销，但提升遍历开销。

代码2.0：

class Solution {
   public:    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
           ListNode* cur1 = l1;        ListNode* cur2 = l2;        int len1 = 0;        int len2 = 0;        bool isCarry = false;        while (cur1 != NULL) {
               ++len1;            cur1 = cur1->next;        }        while (cur2 != NULL) {
               ++len2;            cur2 = cur2->next;        }        cur1 = len1 >= len2 ? l1 : l2;        cur2 = len1 >= len2 ? l2 : l1;        ListNode* pre = cur1;        while (cur2 != NULL) {
               int total = cur1->val + cur2->val + isCarry;            if (total >= 10) {
                   total -= 10;                isCarry = true;            }            else isCarry = false;            pre = cur1;            cur1->val = total;            cur1 = cur1->next;            cur2 = cur2->next;        }        while (cur1 != NULL) {
               if (cur1->val == 9 && isCarry) {
                   cur1->val = 0;                isCarry = true;            }            else {
                   cur1->val += isCarry;                isCarry = false;            }            pre = cur1;            cur1 = cur1->next;        }        if (isCarry) {
               ListNode* newNode = new ListNode(1);            pre->next = newNode;;        }        return len1 >= len2 ? l1 : l2;    }};

效率还是不理想。。

转载地址：http://rpowi.baihongyu.com/