题解 | #两个链表生成相加链表#

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//我又呦呦呦又来水题解了（也算是做一下笔记吧）
//首先讲下这题主要思路，嗯，合并两个链表，其实本质上就是大整数求和，即，先遍历两个链表
//用两个数组存储链表中的元素（吐槽一下，这个数组有必要开那么大吗？意思一下不就行了），
//然后就是大整数求和那一套了，不会的同学自行复习数据结构哦，不过这题还有一个小考点就是最后链表要用头插法而不能用尾插法（小坑）。
class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        int array1[1000001],array2[1000001],flag1=0,flag2=0;
        ListNode *p=head1;
        while(p)//遍历，存储元素
        {
            array1[flag1++]=p->val;
            p=p->next;
        }
        p=head2;
        while(p)//遍历，存储元素到数组中
        {
            array2[flag2++]=p->val;
            p=p->next;
        }
        ListNode *NewHead=NULL;//这个就是我们要返回的链表头指针
        int flag=0;//进位标志
        flag1--;flag2--;
        while(flag1>=0&&flag2>=0)//大整数求和，我就不讲了，百度or看书
        {
            int data=(array1[flag1]+array2[flag2]+flag)%10;
            flag=(array1[flag1--]+array2[flag2--]+flag)/10;
            ListNode *s=new ListNode(data);
            s->next=NewHead;//头插法，因为我们是从最后开始加的嘛，所以你先加的肯定要排在最后嘛（想不通自己写两个柿子加一下）
            NewHead=s;
        }
        while(flag1>=0)
        {
            int data=(array1[flag1]+flag)%10;
            flag=(array1[flag1--]+flag)/10;
            ListNode *s=new ListNode(data);
            s->next=NewHead;
            NewHead=s;
        }
        while(flag2>=0)
        {
            int data=(array2[flag2]+flag)%10;
            flag=(array2[flag2--]+flag)/10;
            ListNode *s=new ListNode(data);
            s->next=NewHead;
            NewHead=s;
        }
        if(flag==1)
        {
            ListNode *s=new ListNode(1);
            s->next=NewHead;
            NewHead=s;
            return NewHead;
        }
        return NewHead;//返回头指针，结束（水完，有要接着做了，库鲁西）
    }
};