C++刷题笔记4

P.S 非科班出身，对C++和算法较陌生，从入门开始，使用的是牛客网平台，刷题借鉴了很多前人的思路，博客仅为记录用。

问题描述：假设链表中每一个节点的值都在 0 − 9 0 - 9 0−9之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围： 0 ≤ n , m ≤ 1000000 0≤n,m≤1000000 0≤n,m≤1000000 ，链表任意值 0 ≤ v a l ≤ 9 0≤val≤9 0≤val≤9
例如：链表1为9->3->7，链表2为6->3，最后生成新的结果链表为1->0->0->0。
问题要求：空间复杂度 O ( n ) O(n) O(n)，时间复杂度 O ( n ) O(n) O(n)
解题思路：借鉴了网站的思路，分两步走，单独写函数用于链表反转，反转链表见参考资料1，然后进行加法操作，与整数加法法则相同，从个位数加起，最后对结果做一次反转。
代码：

class Solution {
public:
    
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        ListNode* re_head1 = reverseList(head1);
        ListNode* re_head2 = reverseList(head2);
        ListNode* new_list = new ListNode(0);
        ListNode* new_head = new_list;
        int n1,n2;
        int carry = 0;
        int sum = 0;
        while (re_head1 != nullptr || re_head2 != nullptr || carry != 0){
            if (re_head1 == nullptr)
                n1 = 0;
            else {
                n1 = re_head1->val;
                re_head1 = re_head1->next;
            }
            
            if (re_head2 == nullptr)
                n2 = 0;
            else {
                n2 = re_head2->val;
                re_head2 = re_head2->next;
            }
            sum = n1 + n2 + carry;
            new_list->next = new ListNode(sum%10);
            carry = sum/10;
            new_list = new_list->next;
        }
        ListNode* renew_head = reverseList(new_head->next);
        return renew_head; 
    }
    
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur != nullptr) {
            ListNode* tmp = cur->next;           //tmp指向原列表下一个指针，连接着第三个
            cur->next = pre;                     //原列表下一位指向pre，得到cur->pre
            pre = cur;                           //pre指向cur,得到cur->pre(此时pre储存着原列表的表头值)
            cur = tmp;                           //cur内部指针指向原列表第二位
        }
        return pre;
    }
};

注意点：

1. ListNode* new_list = new ListNode(0); ListNode* new_head = new_list;将链表new_list初始节点设置为0，并将new_head指向此0的节点，记录链表初始位置；
2. 想要在链表里添加新的元素，一定要先挖好坑，即链表本身无next，需要指定节点如：new_list->next = new ListNode(sum%10)，指的是原链表下一位连接到储存sum%10的节点处，否则会内存溢出。

参考资料:

1. 单链表反转详解（4种算法实现）
2. 哨兵节点
3. C++链表及其创建