leetcode 第2题 Add Two Numbers

题目地址

https://leetcode.com/problems/add-two-numbers/description/

题目描述

/*
 * @lc app=leetcode id=2 lang=c
 *
 * [2] Add Two Numbers
 *
 * https://leetcode.com/problems/add-two-numbers/description/
 *
 * algorithms
 * Medium (31.15%)
 * Total Accepted:    883.2K
 * Total Submissions: 2.8M
 * Testcase Example:  '[2,4,3]\n[5,6,4]'
 *
 * You are given two non-empty linked lists representing two non-negative
 * integers. 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.
 *
 * You may assume the two numbers do not contain any leading zero, except the
 * number 0 itself.
 *
 * Example:
 *
 *
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * Explanation: 342 + 465 = 807.
 *
 *
 */


/*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

思路

这道题考察链表的相关知识.题目是逆序存储,正好实现了由低位向高位相加,和正常的计算顺序一样.
如果一个链表为空,则返回另外一个链表;如果两个链表都不为空,两个链表对应的值相加.当一个链表没有数据时,需要加上另外
一个链表值;如果结束时还有进位,则要再开辟一个节点存储产生的进位.
此类题目有一个通用的结构:

while(L1 && L2){
    ....    // 处理L1和L2都不为空的情况
}
while(L1){
    ....    // 处理当L2为空并且L1不为空的情况
}
while(L2){
    ....    // 处理当L1为空并且L2不为空的情况
}

if(carry){
    ....   // 如果有进位的话
}

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//a file named add-two-numbers.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Definition for singly-linked list. */
struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode *pre = NULL, *head = NULL, *res = NULL;
    int carry = 0;
    if(l1 == NULL && l2 == NULL)
        return NULL;
    if(l1 == NULL && l2 != NULL)
        return l2;
    if(l1 != NULL && l2 == NULL)
        return l1;
    while(l1 && l2){
        if(pre == NULL){
            head = res =(struct ListNode*)malloc(sizeof(struct ListNode));
        }
        else{
            res = (struct ListNode*)malloc(sizeof(struct ListNode));
            pre->next = res;
        }
        res->val = (l1->val + l2->val + carry) % 10;
        carry = (l1->val + l2->val + carry) / 10;

        l1 = l1->next;
        l2 = l2->next;
        res->next = NULL;
        pre = res;
    }
    while(l1){
        res = (struct ListNode*)malloc(sizeof(struct ListNode));
        res->val = (l1->val + carry) % 10;
        carry = (l1->val + carry) / 10;
        pre->next = res;
        res->next = NULL;
        l1 = l1->next;
        pre = res;
    }
    while(l2){
        res = (struct ListNode*)malloc(sizeof(struct ListNode));
        res->val = (l2->val + carry) % 10;
        carry = (l2->val + carry) / 10;
        pre->next = res;
        res->next = NULL;
        l2 = l2->next;
        pre = res;
    }
    if(carry > 0){
        res = (struct ListNode*)malloc(sizeof(struct ListNode));
        res->val = carry;
        res->next = NULL;
        pre->next = res;
    }
    return head;
}

static struct ListNode *createNode(char *digits)
{
    struct ListNode *res, *p, *prev;
    int i = 0, first = 1;
    int len = strlen(digits);
    char *c = digits;
    prev = NULL;
    while (i < len) {
        p = (struct ListNode *)malloc(sizeof(struct ListNode));
        if (first) {
            first = 0;
            res = p;
        }
        p->val = *(c++) - '0';
        p->next = NULL;
        if (prev != NULL) {
            prev->next = p;
        }
        prev = p;
        i++;
    }

    return res;
}

void printShow(struct ListNode *ln)
{
    while (ln != NULL) {
        printf("%d",ln->val);
        ln = ln->next;
    }
    printf("\n");
}

void clearList(struct ListNode ** L )
{
    struct ListNode *temp, *pNext;
    temp = (*L);
    while(temp){
        pNext = temp->next;
        free(temp);
        temp = pNext;
    }
}


int main(int argc, char **argv)
{
    if (argc < 3) {
        fprintf(stderr, "Usage: ./test n1 n2     (for example: ./test 243 564)\n");
        exit(-1);
    }

    struct ListNode *l1 = createNode(argv[1]);
    struct ListNode *l2 = createNode(argv[2]);
    struct ListNode *res = addTwoNumbers(l1, l2);
    printShow(res);
    clearList(&l1);
    clearList(&l2);
    clearList(&res);
    return 0;
}

编译并运行:

haha@hello:~$ gcc -g -o add-two-numbers add-two-numbers.c
haha@hello:~$ ./add-two-numbers 243 564
708
haha@hello:~$ ./add-two-numbers 112 359
4611
haha@hello:~$