题解 | #链表相加(二)#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <memory>
#include <stack>

class Solution {
 public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   * 该题的关键是引入stack栈的数据，这样就迎刃而解。
   *
   * @param head1 ListNode类
   * @param head2 ListNode类
   * @return ListNode类
   */

  std::stack<ListNode*> PushStack(ListNode* head) {
    std::stack<ListNode*> data;
    while (head != nullptr) {
      data.push(head);
      head = head->next;
    }
    return data;
  }

  ListNode* addInList(ListNode* head1, ListNode* head2) {
    // write code here
    auto stack1 = PushStack(head1);
    auto stack2 = PushStack(head2);

    auto virtual_head = new ListNode(-1);
    auto cross = 0;

    auto AddNum = [&virtual_head, &cross](ListNode* temp) {
        auto sum = temp->val + cross;
        if (sum > 9) {
          sum -= 10;
          cross = 1;
        } else {
          cross = 0;
        }

        temp->val = sum;
        temp->next = virtual_head->next;
        virtual_head->next = temp;
    };

    while (!stack1.empty() && !stack2.empty()) {

      auto sum = stack1.top()->val + stack2.top()->val + cross;
      if (sum > 9) {
        cross = 1;
        sum = sum - 10;
      } else {
        cross = 0;
      }

      auto temp = stack1.top();
      temp->val = sum;
      temp->next = virtual_head->next;
      virtual_head->next = temp;

      stack1.pop();
      stack2.pop();
    }

    if (stack1.empty()) {
      while (!stack2.empty()) {
        auto temp = stack2.top();
        AddNum(temp);
        stack2.pop();
      }
    } else {
      while (!stack1.empty()) {
        auto temp = stack1.top();
        AddNum(temp);
        stack1.pop();
      }
    }

    if (cross == 1) {
      virtual_head->val = 1;
      return virtual_head;
    } else {
      auto ret = virtual_head->next;
      delete virtual_head;
      return ret;
    }

  }
};