题解 | 链表相加(二)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    // 反转链表函数
    ListNode* rever(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* nex = nullptr;
        while (cur) {
            nex = cur->next;  // 保存下一个节点
            cur->next = pre;  // 反转当前节点指针
            pre = cur;        // 更新前驱节点
            cur = nex;        // 移动到下一个节点
        }
        return pre;  // 返回新头节点（原尾节点）
    }

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // 反转两个链表，使低位在前
        ListNode* p1 = rever(head1);
        ListNode* p2 = rever(head2);
        
        // 创建虚拟头节点，简化链表操作
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;  // 当前节点指针
        int carry = 0;          // 进位标志（初始为0）

        // 遍历两个链表，处理所有节点和进位
        while (p1 != nullptr || p2 != nullptr || carry != 0) {
            // 计算当前位总和（节点值+进位）
            int sumVal = carry;
            if (p1 != nullptr) {
                sumVal += p1->val;
                p1 = p1->next;  // 移动到下一位
            }
            if (p2 != nullptr) {
                sumVal += p2->val;
                p2 = p2->next;  // 移动到下一位
            }

            // 计算当前位值和新进位
            carry = sumVal / 10;        // 进位（0或1）
            int currentVal = sumVal % 10;  // 当前位值（个位）

            // 创建新节点并拼接
            cur->next = new ListNode(currentVal);
            cur = cur->next;  // 移动到新节点
        }

        // 反转结果链表，恢复高位在前的顺序
        ListNode* result = rever(dummy->next);
        return result;
    }
};