题解 | 链表相加(二)

/**
 * 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* reverse_node(ListNode* phead){
        if(phead == nullptr || phead->next == nullptr){
            return phead;
        }
        ListNode * new_head = reverse_node(phead->next);
        phead->next->next = phead;
        phead->next = nullptr;
        return new_head;
	}
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        auto result_list = new ListNode(-1);
        ListNode* p = result_list;
        ListNode* tmp1 = reverse_node(head1);
        // cout << tmp1->val << " ";
        ListNode* tmp2 = reverse_node(head2);
        // cout << tmp2->val << " ";
     
        int val=0;
        int carry = 0;
	  //当两个指针都不为空，或者还有进位的情况，循环继续
        while(tmp1 != nullptr || tmp2 != nullptr || carry == 1){
            int val1 = tmp1 != nullptr ? tmp1->val : 0;
            int val2 = tmp2 != nullptr ? tmp2->val : 0;
            //9+0+1
            val = val1 + val2 + carry;
            cout << val << " ";
            carry = val / 10;
            val = val % 10;
            p->next = new ListNode(val);
            p = p->next;
            if(tmp1 != nullptr)
                tmp1 = tmp1->next;
            if(tmp2 != nullptr)
                tmp2 = tmp2->next;
        }
	  //跳过头节点，然后反转
        result_list = reverse_node(result_list->next);
        return result_list;
    }
};