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

感觉写的很烂。。。虽然思路简单易懂，但是逻辑太重复罗嗦了！

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
  public:
    ListNode* addInList(ListNode* head1, ListNode* head2) {
      if (head1 == nullptr || head2 == nullptr) {
        return head1 == nullptr ? head2 : head1;
      }
      
      std::stack<ListNode *> r_list1, r_list2;
      ListNode *list1 = head1, *list2 = head2, *head = nullptr;
      char flag = '1';
      
      while (list1 && list2) {
        r_list1.push(list1);
        r_list2.push(list2);
        
        list1 = list1->next;
        list2 = list2->next;
      }
      
      if (list1) {
        while (list1) {
          r_list1.push(list1);
          list1 = list1->next;
        }
      }
      
      if (list2) {
        flag = '2';
        while (list2) {
          r_list2.push(list2);
          list2 = list2->next;
        }
      }
      
      if (flag == '1') {
        head = add_list(r_list1, r_list2);
      } else {
        head = add_list(r_list2, r_list1);
      }
      
      return head;
    }
  private:
    ListNode *add_list(std::stack<ListNode *> &l_list, std::stack<ListNode *> &s_list) {
      bool flag = false;
      ListNode *node = nullptr;
      
      while (!s_list.empty()) {
        node = l_list.top();
        node->val += s_list.top()->val;
        s_list.pop();
        l_list.pop();
        if (flag) {
          ++(node->val);
          flag = false;
        }
        if (node->val > 9) {
          node->val %= 10;
          flag = true;
        }
      }
      
      
      if (flag) {
        node = l_list.top();
        node->val += 1;
        flag = false;
        while (!l_list.empty()) {
          node = l_list.top();
          if (flag) {
            node->val += 1;
            flag = false;
          }
          if (node->val > 9) {
            flag = true;
            node->val %= 10;
          }
          l_list.pop();
        }
      } else {
        while (!l_list.empty()) {
          node = l_list.top();
          l_list.pop();
        }
        return node;
      }
      
      if (flag) {
        node->val %= 10;
        ListNode *new_head = new ListNode(1);
        new_head->next = node;
        node = new_head;
      } 
      
      return node;
    }
};