C语言模拟链表加法

"手稿_V1.02 - 链表加法的C语言实现" 在计算机科学中，链表是一种常见的数据结构，用于存储一系列元素。本问题涉及的链表是逆序存储非负整数的每一位的，即每个节点只包含一个数字。题目要求在C语言环境下实现两个这样的链表相加的功能，不考虑前导零。这个问题通常被称为“两数相加”（Add Two Numbers），源自LeetCode的热门题目。 首先，我们需要理解链表的结构。一个链表节点通常由两部分组成：一个存储值的变量（如`int val`）和一个指向下一个节点的指针（如`struct ListNode* next`）。在C语言中，我们定义链表节点的结构体如下： ```c struct ListNode { int val; struct ListNode* next; }; ``` 为了实现链表加法，我们可以遵循以下步骤： 1. **创建头节点**：由于我们需要返回一个新的链表，所以先创建一个头节点`head`，初始值设为0，其`next`指针指向`NULL`。 2. **初始化尾巴节点**：创建一个`tail_node`指针，最初设置为`head`，用于跟踪新链表的末尾。 3. **遍历链表**：使用`while`循环，通过`state_words`变量追踪两个链表的状态。`state_words`可以取0、1或2，分别表示两个链表都为空、只有l1或只有l2。 4. **逐位相加**：在每次循环中，根据`state_words`的值，为每个链表创建新的节点（如果对应链表非空），将两个节点的值相加，加上进位`carry_flag`。计算结果可能需要进行进位处理，因此需要保持一个进位标志。 5. **更新状态**：根据计算结果更新新链表的节点值，如果存在进位，将进位传递到下一次循环。 6. **连接节点**：将新创建的节点添加到`tail_node`后面，然后更新`tail_node`为新节点。 7. **处理进位**：如果当前位的和大于9，需要进行进位，更新`carry_flag`。 8. **结束条件**：当两个链表均遍历完且无进位时，循环结束。 9. **返回结果**：最后返回`head->next`，因为`head`是为了初始化而创建的，实际的链表从`head->next`开始。 以下是简化的代码实现： ```c struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { struct ListNode head = {0, NULL}; struct ListNode* tail_node = NULL; struct ListNode* temp = NULL; int carry_flag = 0; // 初始化 tail_node = &head; while (l1 || l2 || carry_flag) { // 创建新节点并计算值 temp = (struct ListNode*)malloc(sizeof(struct ListNode)); temp->val = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry_flag; carry_flag = temp->val / 10; temp->val %= 10; // 连接新节点到链表尾部 tail_node->next = temp; tail_node = temp; // 移动指针 if (l1) l1 = l1->next; if (l2) l2 = l2->next; } return head.next; } ``` 这个函数实现了链表加法的逻辑，遵循了逆序存储数字位的原则，同时处理了进位的情况。在实际编程中，记得在完成操作后释放不再需要的内存，以防止内存泄漏。