题解 | 链表相加(二)

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
//ReverseList用于翻转链表
    ListNode* ReverseList(ListNode* head) {
        ListNode* n1 = nullptr;
        ListNode* n2 = head;
        if (n2 == nullptr) {
            return head;
        }
        ListNode* n3 = head->next;

        while (n2) {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n2)//这里需要注意
                n3 = n2->next;
        }
        return n1;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        ListNode* ptr1 = ReverseList(head1);//9->3->7 ----- 7->3->9
        ListNode* ptr2 = ReverseList(head2);//6->3 -----    3->6
        int ret = 0;
        ListNode* head = nullptr;//相加之后的链表
        ListNode* ptr = head;
        int count = 1;//用来记录头节点
        while (ptr1 || ptr2) {
            int sum = 0;
            if (ptr1) {
                sum += ptr1->val;
                ptr1 = ptr1->next;
            }
            if (ptr2) {
                sum += ptr2->val;
                ptr2 = ptr2->next;
            }
            sum += ret;
            //创建节点；
            ListNode* cur = new ListNode(sum % 10);
            if (count == 1) {
                head = cur;
                ptr = head;
                ret = sum / 10;
                count++;
            } else {
                ptr->next = cur;
                ptr = cur;
                ret = sum / 10;
            }
        }
        if (ret) {
            ListNode* cur = new ListNode(ret);
            ptr->next = cur;
        }
        return ReverseList(head);//最后需要将链表翻转
    }
};