题解 | 链表相加(二)

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstdio>
class Solution {
  public:
    ListNode* reversalList(ListNode* p1) {
        if (p1 == nullptr || p1->next == nullptr) {
            return p1;
        }
        ListNode* tempPtr = p1->next;
        p1->next = nullptr;
        while (tempPtr) {
            ListNode* thirdPtr = tempPtr->next;
            tempPtr->next = p1;
            p1 = tempPtr;
            tempPtr = thirdPtr;
        }
        return p1;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        ListNode* h1 = reversalList(head1);
        ListNode* h2 = reversalList(head2);
        ListNode* result_head = new ListNode(0);
        ListNode* result_head_index = result_head;
        int shang = 0;
        int remainder = 0;
        while (h1 && h2) {
            int temp_number = h1->val + h2->val + shang;
            shang = temp_number / 10;
            remainder = temp_number % 10;
            ListNode* tempPtr = new ListNode(remainder);
            result_head->next = tempPtr;
            result_head = result_head->next;
            h1 = h1->next;
            h2 = h2->next;
        }
        if (h1 == nullptr) {
            while (h2) {
                int temp_number = h2->val + shang;
                shang = temp_number / 10;
                remainder = temp_number % 10;
                ListNode* tempPtr = new ListNode(remainder);
                result_head->next = tempPtr;
                result_head = result_head->next;
                h2 = h2->next;
            }
        } else if (h2 == nullptr) {
            while (h1) {
                int temp_number = h1->val + shang;
                shang = temp_number / 10;
                remainder = temp_number % 10;
                ListNode* tempPtr = new ListNode(remainder);
                result_head->next = tempPtr;
                result_head = result_head->next;
                h1 = h1->next;
            }
        }
        if (shang == 1) {
            ListNode* tempPtr = new ListNode(shang);
            result_head->next = tempPtr;
            result_head = result_head->next;
        }
        return reversalList(result_head_index->next);
    }
};

因为链表没办法从末尾直接读取数据，可以将链表反转或者借助栈，两种方法最后的加法思路都是计算商和余数