题解 | 链表相加(二)

/**
 * 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) {
        if (!head1 || !head2) return head1 ? head1 : head2;  // 处理空指针

        // 动态数组存储节点值
        vector<int> A1, A2, A3;
        ListNode* p1 = head1, *p2 = head2;

        // 将链表值存入数组
        while (p1) { A1.push_back(p1->val); p1 = p1->next; }
        while (p2) { A2.push_back(p2->val); p2 = p2->next; }

        // 相加并处理进位
        int i = A1.size() - 1, j = A2.size() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += A1[i--];
        if (j >= 0) sum += A2[j--];
        A3.push_back(sum % 10);
        carry = sum / 10;
        }

        // 构建结果链表
        ListNode* p3 = new ListNode(0);  // 头节点
        ListNode* cur = p3;
        for (int k = A3.size() - 1; k >= 0; --k) {
          cur->next = new ListNode(A3[k]);
          cur = cur->next;
        }
        return p3->next;  // 返回实际头节点
    }
};