题解 | #链表相加(二)#

C语言版本

struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {

    // write code here

    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));

    dummyHead->val = 0;

    int List1Count = 0, List2Count = 0;

    struct ListNode* tmp, *longList, *shortList;

    int ov = 0;             //overflow  进位标志

    /* 模拟栈：先入后出 */

    int st1_i = -1, st2_i = -1, st_i, st_i_tmp;

    // int st1[15]={0}, st2[15]={0}, st[15]={0};  // 本地调试用

    int *st1, *st2, *st;    //st1是较长的链表的栈，st2是较短的链表的栈，st是相加后存储的栈，st需要比st1大，防止相加后进位

    tmp = head1;        //获得head1的长度

    while(tmp){

        tmp = tmp->next;

        List1Count++;

    }

    tmp = head2;        //获得head2的长度

    while(tmp){

        tmp = tmp->next;

        List2Count++;

    }

    //根据head1 head2的长度，分别给st1\st2\st申请空间

    st1 = (int*)malloc(sizeof(int)*(List1Count >= List2Count ? (List1Count+1) : (List2Count+1)));

    st2 = (int*)malloc(sizeof(int)*(List1Count >= List2Count ? (List2Count+1) : (List1Count+1)));

    st  = (int*)malloc(sizeof(int)*(List1Count >= List2Count ? (List1Count+2) : (List2Count+2)));

    if(List1Count >= List2Count){   //根据长度，将head1、2用longList shortList来装，方便后面操作

        longList = head1;

        shortList = head2;

    }else{

        longList = head2;

        shortList = head1;

    }

    tmp = longList;                 //将长链表的值一个个入栈

    while(tmp){

        st1[++st1_i] = tmp->val;

        tmp = tmp->next;

    }

    printf("\r\nst1:  ");           //打印st1，查看是否正确

    for(int i=0;i<st1_i;i++)printf("%d",st1[i]);

    tmp = shortList;                //将短链表的值一个个入栈

    while(tmp){

        st2[++st2_i] = tmp->val;

        tmp = tmp->next;

    }

    printf("\r\nst2:  ");

    for(int i=0;i<st2_i;i++)printf("%d",st2[i]);

    st_i = st1_i+1;                 //长链表st1的索引加一，赋值为结果栈st的索引，加一是为了防止进位

    st_i_tmp = st_i;                    

    dummyHead->next = longList;     //将虚拟头节点的下一个指向长链表，虚拟头节点可用来装进位

    while(st1_i >= 0 || st2_i >= 0 || ov){  //判断栈st1 st2 是否空，ov进位标志是否存在

        if(st1_i >= 0 && st2_i >= 0){       //1、当st1 st2均不为空

            if(st1[st1_i] + st2[st2_i] + ov > 9){       //栈顶值相加并加上进位标志，大于9表示溢出，有进位

                st[st_i_tmp] = st1[st1_i] + st2[st2_i] + ov - 10;

                ov = 1;                                 //赋值ov

            }else{                                       //没有进位溢出，ov置0

                st[st_i_tmp] = st1[st1_i] + st2[st2_i] + ov;

                ov = 0;

            }

        }else if(st1_i >= 0 && st2_i < 0){//2、当st2为空，因为st1是长链表的栈，因此总是st2先空

            if(st1[st1_i] + ov > 9){

                st[st_i_tmp] = st1[st1_i] + ov - 10;

                ov = 1;

            }else{

                st[st_i_tmp] = st1[st1_i] + ov;

                ov = 0;

            }

        }else if(st1_i < 0 && st2_i < 0){  //3、当st1 st2均为空，此时还能进入循环说明有ov，因此将st当前位设为ov（也就是1）

            st[st_i_tmp] = ov;

            ov = 0;

        }

        st1_i--, st2_i--, st_i_tmp--;   //栈索引-1

    }

    tmp = dummyHead;                    //将st结果栈的值一个个赋值为链表(dummyHead->longList)

    for(int i=0; i<=st_i; i++){

        tmp->val = st[i];

        tmp = tmp->next;

    }

    tmp = NULL;                         //末尾置NULL

    if(st[0] == 1)                      //根据st结果栈的元素进行判断，是否有进位导致链表延长1，

        return dummyHead;               //有延长就返回赋值好的虚拟头节点dummyHead

    else

        return dummyHead->next;         //没有进位则返回dummyHead->next，即longList

}