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

代码核心部分与前面的大数加法一样，只是多了个链表与数组之间的转换，属于笨方法

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head1 ListNode类
 * @param head2 ListNode类
 * @return ListNode类
 */
#include <stdio.h>
#include <stdlib.h>

struct ListNode* arrayToList(int arr[], int maxlen) {
    // 创建链表头节点并初始化
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (arr[0] == 0) {//第一位为0代表实际结果没有第一位
        head->val = arr[1];
        head->next = NULL;
    } else {
        head->val = arr[0];
        head->next = NULL;
    }

    struct ListNode* current = head; // current指向当前节点

    int i = 0;
    if (arr[0] == 0) {
        i++;
    }
    // 遍历数组并将其元素转换为链表节点
    for (; i < maxlen; i++) {
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(
                                       struct ListNode)); // 创建新节点
        newNode->val = arr[i]; // 设置节点值
        newNode->next = NULL; // 将节点的next指针初始化为NULL

        current->next = newNode; // 将新节点连接到当前节点的后面
        current = newNode; // 将current指针移到新节点
    }

    return head->next; // 返回链表指针
}

struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    struct ListNode* p1 = head1;
    struct ListNode* p2 = head2;
    int a[1000000] = {0};
    int b[1000000] = {0};

    int len1 = 0, len2 = 0, maxlen = 0;
    int i = 0, j = 0;

    while (p1 != NULL) {
        a[i++] = p1->val;
        p1 = p1->next;
        len1++;
    }
    while (p2 != NULL) {
        b[j++] = p2->val;
        p2 = p2->next;
        len2++;
    }

    if (len1 == 0&&len2==0) {//两个空数组直接返回空
        return NULL;
    }

    maxlen = (len1 > len2) ? len1 : len2;

    int result[maxlen + 1]; //结果数组并初始化为0
    memset(result, 0, maxlen + 1);

    int carry = 0; // 进位
    i = len1 - 1;
    j = len2 - 1;
    int k = maxlen;

    while (i >= 0 || j >= 0 || carry > 0) {
        int digit1 = (i >= 0) ? a[i] : 0; //长度不足的在前面补0
        int digit2 = (j >= 0) ? b[j] : 0;

        int sum = digit1 + digit2 + carry;
        result[k] = sum % 10;
        carry = sum / 10;
        i--;
        j--;
        k--;
    }

    struct ListNode* finalresult = arrayToList(result, maxlen+1);//结果链表

    return finalresult;
}