在链表中添加两个数字时发出结转

Question

我正在解决leetcode问题，在链表中添加两个数字。

以下是我的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* node1 = l1;
        ListNode* node2 = l2;

        if(!node1 && !node2){
            return l1;
        }
        if(!node1){
            return l2;
        }
        if(!node2){
            return l1;
        }
        while(node1 && node2){
                node1->val = node1->val + node2->val;
                node1 = node1->next;
                node2 = node2->next;    
        }
        if(!node1 && !node2){
            return l1;
        }
        if(!node2){
            node1 = node1->next;
        }
        if(!node1){
            node1 = node2;
        }
        node1 = l1;
        if(!node1){
            return l1;
        }
        while(l1->next != nullptr){
            if(l1->val >9){
                l1->next->val += (l1->val)/10;
                l1->val = l1->val%10;
            }
            l1 = l1->next;
        }
        ListNode* abc = new ListNode();
        if(l1->next == nullptr && l1->val>9){
            l1->next = abc;
            abc->val = (l1->val)/10;
            l1->val = l1->val%10;

        }
        return node1;
    }
};

当 l1 的测试用例值为 [8,8,8] 且 l2 为 [2,2] 时，我得到 [0,1,9]，这是正确的预期结果，但如果我将测试用例修改为 [8 ,8,6] 和 [2,2,2]，我得到的总和为 [10,10,8]。 同样，我得到了 l1 = [2,4,3] 和 l2 = [5,6,4] 的错误答案，但我不明白为什么。

Answer 1

有几个问题：

• 在第一个循环之后，您将看到以下代码：

      if(!node1 && !node2){
          return l1;
      }
  

  但是如果

  return

  被执行，你还没有检查是否有任何节点值溢出。因此，您最终可能会得到一些具有 10 或更多值的节点。所以这个代码块必须被删除。

• 接下来的两个

  if

  块没有完成任何事情：

      if(!node2){
          node1 = node1->next;
      }
      if(!node1){
          node1 = node2;
      }
  

  他们打算将最长列表的剩余部分附加到

  l1

  列表中，但这些分配仅分配给变量；他们没有改变链表中的任何指针。为此，您需要知道前一个节点是什么，以便可以更新其

  next

  字段。但是您不再有对前一个节点的引用...要解决这个问题，请确保提前一步退出第一个循环，以便

  node1

  和

  node2

  都还不是

  nullptr

  ，而是一个其中是它们所在列表的尾节点。

• 完成

  node1 = l1

  后，您检查

  node1

  是否为

  nullptr

  ，但这永远不会是真的，因为您在函数顶部检查了这一点。

• 不是问题，但在这个声明中：

  if(l1->next == nullptr && l1->val>9){
  

  ...第一个条件保证为真，因此您可以将此代码简化为：

  if(l1->val>9){
  

可以对您的代码提出更多评论，但这是解决上述要点的版本：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* node1 = l1;
        ListNode* node2 = l2;
        if(!node1 && !node2){
            return l1;
        }
        while (node1->next && node2->next){ // Stop when arriving at a tail node
            node1->val = node1->val + node2->val;
            node1 = node1->next;
            node2 = node2->next;    
        }
        node1->val = node1->val + node2->val; // Also update that node
        if(!node1->next){ // If the first list is the shortest
            node1->next = node2->next; // then attach the remaining nodes to it
        }
        node1 = l1;
        while(l1->next != nullptr){
            if(l1->val >9){
                l1->next->val += (l1->val)/10;
                l1->val = l1->val%10;
            }
            l1 = l1->next;
        }
        ListNode* abc = new ListNode();
        if(l1->val>9){
            l1->next = abc;
            abc->val = (l1->val)/10;
            l1->val = l1->val%10;
        }
        return node1;
    }
};

下一个改进是将两个循环连接到一个循环中，以便在存储总和时立即处理进位。