2.Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

该题的算法就是实现大数相加,不过数是低位在前,高位在后存储的。例题是:342 + 465 = 807。

我写的第一个算法是:

/*
* You are given two linked lists representing two non-negative numbers.
* The digits are stored in reverse order and each of their nodes contain
* a single digit. Add the two numbers and return it as a linked list.
* Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
* Output: 7 -> 0 -> 8
*/
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/

#include <stdio.h>
#include <math.h>

typedef struct ListNode ListNode;
struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    int val1 = 0;
    int val2 = 0;
    int c = 0; // 该变量存储进位
    struct ListNode *result = NULL;     // 存储结果的链表的首地址
    struct ListNode *temp = NULL;       // 暂时存储相加的结果
    struct ListNode *tail = NULL;       // 指向链表的最后一个节点
    while (l1 != NULL || l2 != NULL) {
        val1 = 0;
        if (l1 != NULL) {
            val1 = l1->val;
            l1 = l1->next;
        }
        val2 = 0;
        if (l2 != NULL) {
            val2 = l2->val;
            l2 = l2->next;
        }
        temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        memset(temp, 0, sizeof(struct ListNode));
        temp->val = (val1 + val2 + c) % 10;
        c = (val1 + val2 + c) / 10;
        if (result == NULL) {
            result = temp;
            tail = temp;
        }
        else {
            tail->next = temp;
            tail = temp;
        }
    }
    if (c > 0) {
        temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        memset(temp, 0, sizeof(struct ListNode));
        temp->val = 1;
        tail->next = temp;
    }
    return result;
}

struct ListNode* creatList(int* array, int arrayLength) {
    int i;
    struct ListNode* tail = NULL;
    struct ListNode* temp = NULL;
    struct ListNode* list = NULL;
    for (i = 0; i < arrayLength; i++) {
        temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        memset(temp, 0, sizeof(struct ListNode));
        temp->val = array[i];
        if (i == 0) {
            list = temp;
            tail = temp;
        }
        else {
            tail->next = temp;
            tail = temp;
        }
    }
    return list;
}

void showList(struct ListNode* list) {
    while (list) {
        if (list != NULL && list->next != NULL) {
            printf("%d ->", list->val);
        }
        else {
            printf("%d\n", list->val);
        }
        list = list->next;
    }
}

int main() {
    struct ListNode* l1, *l2, *sum;
    int a[] = { 9, 9, 9, 9 };
    int b[] = { 1 };
    int i;
    l1 = creatList(a, sizeof(a) / sizeof(int));
    l2 = creatList(b, sizeof(b) / sizeof(int));
    showList(l1);
    showList(l2);
    sum = addTwoNumbers2(l1, l2);
    showList(sum);
    scanf_s("%d", &i);
    return 0;
}

这个算法虽然通过了,但是算法的时间是20多毫秒,仅仅超过了24%的算法。经过研究之后发现,上面算法中内存开辟的太多,因此可以通过减少动态开辟内存来降低时间。可以将计算结果存储在原来的链表里节省内存,即实现原位存储。改进的算法如下:

// 使用原位存储的思想,尽量少开辟内存
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    int val1 = 0;
    int val2 = 0;
    int c = 0; // 该变量存储进位
    struct ListNode *result = NULL;     // 存储结果的链表的首地址
    struct ListNode *temp = NULL;       // 暂时存储相加的结果
    struct ListNode *tail = NULL;       // 指向链表的最后一个节点
    while (l1 != NULL || l2 != NULL) {
        if (l1 != NULL && l2 != NULL) {
            l1->val = (l1->val + l2->val + c);
            c = l1->val / 10;
            l1->val = l1->val % 10;
            if (result == NULL) {
                result = l1;
                tail = l1;
            }
            else {
                tail->next = l1;
                tail = l1;
            }
            l1 = l1->next;
            l2 = l2->next;
        }
        if (l1 == NULL && l2 != NULL) {
            l2->val = (l2->val + c);
            c = l2->val / 10;
            l2->val = l2->val % 10;
            tail->next = l2;
            tail = l2;
            l2 = l2->next;
        }
        if (l1 != NULL && l2 == NULL) {
            l1->val = (l1->val + c);
            c = l1->val / 10;
            l1->val = l1->val % 10;
            tail->next = l1;
            tail = l1;
            l1 = l1->next;
        }
    }
    if (c > 0) {
        temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        memset(temp, 0, sizeof(struct ListNode));
        temp->val = 1;
        tail->next = temp;
    }
    return result;
}

提交之后,程序运行时间是16ms。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

6 + 11 =

1 + 3 =