C语言实现两数相加解决方案

资源摘要信息:"两数相加问题是一个经典的编程问题，通常出现在面试和编程竞赛中，考察程序员的基础编程能力，特别是对链表结构的操作理解。在LeetCode平台上，这个问题被标记为难度中等。该问题描述如下： 给定两个非空链表，用来表示两个非负整数。其中，每个节点包含一个数字，数字按逆序存储，即最低位数字存储在头节点。编写一个函数，将这两个数相加，并以链表形式返回结果。结果同样需要逆序存储在链表中。 此问题的关键是理解链表的结构和遍历链表的算法。链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针（最后一个节点的指针指向NULL）。在本问题中，我们通常会定义一个链表节点的结构体，包含整型的值和指向下一个节点的指针。需要考虑的问题包括： 1. 链表节点的定义 2. 如何遍历两个输入链表 3. 如何处理进位 4. 如何创建新的链表来存储结果 5. 如何处理不同长度的链表 6. 如何优雅地处理链表的边界条件 以下是一个使用C语言实现的示例代码，它定义了链表节点结构体，并实现了上述功能： ```c #include <stdio.h> #include <stdlib.h> // 链表节点的定义 struct ListNode { int val; struct ListNode *next; }; // 创建链表节点 struct ListNode* createNode(int x) { struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode)); newNode->val = x; newNode->next = NULL; return newNode; } // 两数相加函数 struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { struct ListNode dummyHead; dummyHead.next = NULL; struct ListNode *p = &dummyHead; int carry = 0; // 进位 while (l1 != NULL || l2 != NULL) { int x = (l1 != NULL) ? l1->val : 0; int y = (l2 != NULL) ? l2->val : 0; int sum = carry + x + y; carry = sum / 10; p->next = createNode(sum % 10); p = p->next; if (l1 != NULL) l1 = l1->next; if (l2 != NULL) l2 = l2->next; } if (carry > 0) { p->next = createNode(carry); } return dummyHead.next; } // 用于打印链表的辅助函数 void printList(struct ListNode* head) { while (head != NULL) { printf("%d", head->val); head = head->next; } printf("\n"); } // 释放链表内存的辅助函数 void freeList(struct ListNode* head) { struct ListNode* temp; while (head != NULL) { temp = head; head = head->next; free(temp); } } // 主函数示例 int main() { // 示例：创建链表1->2->3 和 4->5->6 struct ListNode* l1 = createNode(1); l1->next = createNode(2); l1->next->next = createNode(3); struct ListNode* l2 = createNode(4); l2->next = createNode(5); l2->next->next = createNode(6); // 相加后的结果应该是 5->7->9 struct ListNode* result = addTwoNumbers(l1, l2); printList(result); // 清理链表内存 freeList(l1); freeList(l2); freeList(result); return 0; } ``` 在这段代码中，首先定义了链表节点的结构体`ListNode`，并提供了创建节点、打印链表和释放链表内存的辅助函数。主要的逻辑实现在`addTwoNumbers`函数中，该函数使用了虚拟头节点技巧，简化了链表操作的复杂性，并且正确处理了进位问题。 在编写代码时，需要注意以下几点： - 如何初始化链表并填充数据 - 如何遍历两个链表，同时处理它们长度不一致的情况 - 如何在遍历过程中处理进位，以及如何在最后一次迭代后处理剩余的进位 - 如何创建新节点来构建结果链表，并在结束后返回这个链表的头节点 - 如何释放动态分配的内存以避免内存泄漏 以上内容是理解和解决“两数相加”问题的关键知识点，涉及数据结构、链表操作以及基础的算术处理。"