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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
      // 栈1栈2 用于逆置head1中的值
      stack<ListNode*> list1;
      stack<ListNode*> list2;
      // 用存放要输出的值
      stack<int> out;

      // 将head1 head2 中的节点依此放入栈中
      auto* it = head1;
      while (it != nullptr) {
        list1.push(it);
        it = it->next;
      }
      it = head2;
      while (it != nullptr) {
        list2.push(it);
        it = it->next;
      }

      // 数据处理 
      // 将栈1 栈2中的值依此取出进行相加
      // next 用于处理进位
      // thiss存放本次要入栈的值
      int next = 0;
      int thiss = 0;
      while(!list1.empty() && !list2.empty()) {
        thiss = list1.top()->val + list2.top()->val + next;
        list1.pop();
        list2.pop();
        next = 0;
        // 若需要进位则next赋值为1 
        if (thiss >= 10) {
            next = 1;
            thiss = thiss % 10;
        }
        out.push(thiss);
      }

      // 若list1 长度大于 list2
      // 处理方法同上
      while (!list1.empty()) {
        int thiss = list1.top()->val + next;
        list1.pop();
        next = 0;
        if (thiss >= 10) {
            next = 1;
            thiss = thiss % 10;
        }
        out.push(thiss);
      }
      
      // 若list1 长度小于 list2
      // 处理方法同上
      while (!list2.empty()) {
        int thiss = list2.top()->val + next;
        list2.pop();
        next = 0;
        if (thiss >= 10) {
            next = 1;
            thiss = thiss % 10;
        }
        out.push(thiss);
      }

      // 处理最末尾数字
      if (next == 1) {
        out.push(1);
      }
      // 数据处理结束 
      // 此时out栈中的数据即为最终输出数据的逆置

      // 重新创建链表存放最终数据
      auto* newHead = new ListNode(0);
      auto* i = newHead;
      while (!out.empty()) {
        i->next = new ListNode(out.top());
        out.pop();
        i = i->next;
      }

      return newHead->next;
    }
};