LeetCode实现两数求和

两数求和是一道经典的算法题，也是很多面试中出现的常见题目。在这篇文章中，我们将介绍LeetCode上两数求和的题目，并给出一些可行的解决方案。

1.题目描述

题目描述如下所示：

给定两个非空的链表，表示两个非负整数。其中每个节点只存储一位数字，将这两个数字相加并以链表形式返回。

假设这两个数字的最高位数字在链表头部。

例如：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 8 -> 0 -> 7

解释：3427 + 465 = 3892，因此结果链表表示的数字为 7893，即 7 -> 8 -> 9 -> 3。

2.解决方案

这道题可以使用多种不同的解决方案。常见的解决方案包括使用递归、迭代和栈。

2.1.递归

使用递归的解决方案可能会更简洁优美。具体来说，我们可以定义一个递归函数，它负责计算两个链表当前节点的和，并将进位值传递到下一次递归调用中。在递归的过程中，我们可以创建一个新节点，将其值设为当前节点的和，然后返回这个新节点。

递归的关键是确定递归停止的条件。在这个问题中，我们需要考虑两个链表都为空的情况，并且当一个链表为空时，我们只需要将另一个链表的节点之和放入结果中。

下面是递归解决方案的示例代码：

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

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    return addTwoNumbersImpl(l1, l2, 0);
}

struct ListNode* addTwoNumbersImpl(struct ListNode* l1, struct ListNode* l2, int carry) {
    if (l1 == NULL && l2 == NULL && carry == 0) {
        return NULL;
    }

    int value = carry;
    if (l1 != NULL) {
        value += l1->val;
        l1 = l1->next;
    }
    if (l2 != NULL) {
        value += l2->val;
        l2 = l2->next;
    }

    struct ListNode* result = (struct ListNode*)malloc(sizeof(struct ListNode));
    result->val = value % 10;
    result->next = addTwoNumbersImpl(l1, l2, value / 10);

    return result;
}

在这个代码中，我们定义了一个addTwoNumbers函数，它将l1和l2传递给addTwoNumbersImpl函数，并将初始进位值设为0。addTwoNumbersImpl函数根据当前节点的值和前一步的进位值，计算当前节点的和，并递归地调用下一个节点。在计算当前节点值时，我们还必须检查链表是否为空，以防止出现空指针错误。最后，我们需要使用malloc函数为结果分配新节点。

2.2.迭代

迭代的解决方案通常比递归更快，因为递归需要产生更多的函数调用。迭代解决方案依次对每一对节点进行相加，并将进位值存储在一个变量中，供下一次迭代使用。遍历完所有节点后，我们要检查进位值是否为0，如果不为0，则需要创建一个新节点。

下面是迭代解决方案的示例代码：

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

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* result = (struct ListNode*)malloc(sizeof(struct ListNode));
    result->val = 0;
    result->next = NULL;

    struct ListNode* tail = result;
    int carry = 0;
    while (l1 != NULL || l2 != NULL) {
        int value = carry;
        if (l1 != NULL) {
            value += l1->val;
            l1 = l1->next;
        }
        if (l2 != NULL) {
            value += l2->val;
            l2 = l2->next;
        }
        carry = value / 10;

        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = value % 10;
        node->next = NULL;
        tail->next = node;
        tail = node;
    }

    if (carry != 0) {
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = carry;
        node->next = NULL;
        tail->next = node;
        tail = node;
    }

    return result->next;
}

在这个代码中，我们首先创建了一个结果节点，该节点的值为0，并且没有任何后继节点。然后我们创建了一个指向结果节点的tail指针，用于追踪最后一个节点。在迭代期间，我们对每对节点执行相加操作，并在尾部插入一个新节点。我们使用carry变量存储进位值，并在下一次循环中使用。如果迭代完成后carry不为零，则需要创建一个新节点并插入结果链表的末尾。

2.3.栈

使用栈也是一种可行的解决方案。首先，我们需要将一对一对的节点以相反的顺序存储在两个栈中（因为输出的数字的高位在前面）。然后我们可以依次将栈中的节点弹出，并执行相加操作和进位操作，并将结果存储在一个新节点上。

下面是栈解决方案的示例代码：

`

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {

struct ListNode* result = NULL;

struct ListNode* tail = NULL;

struct Stack* stack1 = createStack();

struct Stack* stack2 = createStack();

while (l1 != NULL) {

push(stack1, l1->val);

l1 = l1->next;

}

while (l2 != NULL) {

push(stack2, l2->val);

l2 = l2->next;

}

int carry = 0;

while (!isEmpty(stack1) || !isEmpty(stack2)) {

int value = carry;

if (!isEmpty(stack1)) {

value += pop(stack1);

}

if (!isEmpty(stack2)) {

value += pop(stack2);

}

carry = value / 10;

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

node->val = value % 10;

node->next = NULL;

if (tail == NULL) {

result = node;

} else {

tail->next = node;

}

tail = node;

}

if (carry != 0) {

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

node->val = carry;

node->next = result;

result = node;

}

return result;

}

struct Stack {

int *items;

int top;

int size;

};

struct Stack* createStack() {

struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));

stack->size = 1024;

stack->items = (int*)malloc(stack->size * sizeof(int));

stack->top = -1;

return stack;

}

int isEmpty(struct Stack* stack) {

return stack->top == -1;

}

int isFull(struct Stack* stack) {

return stack->top == stack->size - 1;

}

void push(struct Stack* stack, int item) {

if (isFull(stack)) {

return;

}

stack->items[++stack->top] = item;

}

int pop(struct Stack* stack) {

if (isEmpty(stack)) {

return 0;