https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=196&tqId=37147&ru=/exam/oj
class Solution {public:// 逆序链表ListNode* reverse(ListNode* head) {// 创建一个新节点作为逆序后链表的头节点ListNode* newHead = new ListNode(0);// 当前节点指针指向原链表的头节点ListNode* cur = head;// 遍历原链表while (cur) {// 保存当前节点的下一个节点ListNode* next = cur->next;// 将当前节点插入到新链表的头部cur->next = newHead->next;newHead->next = cur;// 更新当前节点为原链表中的下一个节点cur = next;}// 保存逆序后的链表头节点cur = newHead->next;// 释放新节点delete newHead;// 返回逆序后的链表头节点return cur;}ListNode* addInList(ListNode* head1, ListNode* head2) {// 1. 逆序两个链表head1 = reverse(head1);head2 = reverse(head2);// 2. ⾼精度加法int carry = 0; // 进位ListNode* cur1 = head1, *cur2 =head2; // 分别指向两个链表的当前节点ListNode* ret = new ListNode(0); // 结果链表的头节点ListNode* prev = ret; // 指向结果链表当前节点的前一个节点// 遍历两个链表或者进位不为0while (cur1 || cur2 || carry) {if (cur1) {carry += cur1->val;cur1 = cur1->next;}if (cur2) {carry += cur2->val;cur2 = cur2->next;}// 将当前位的数字插入到结果链表中prev = prev->next = new ListNode(carry % 10);carry /= 10; // 更新进位}// 释放结果链表头节点cur1 = ret->next;ret->next = nullptr;delete ret;// 3. 逆序结果链表并返回return reverse(cur1);}
};