有关力扣上两数相加 II的代码漏洞

Question

LCR 025. 两数相加 II
给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]
示例3：

输入：l1 = [0], l2 = [0]
输出：[0]

提示：

链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0

进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。

我的代码（c语言）

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

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode *fir,*sec,*thi;

    if(head==NULL) return NULL;
    else if(head->next==NULL) return head;
    else
    {
    fir = NULL;
    sec = head;
    thi = head->next;
    while(thi!=NULL)
    {
        sec ->next=fir;
        fir=sec;
        sec = thi;
        thi = thi->next;
    }
    sec->next=fir;
    return sec;
    } 
}

struct ListNode* createNode(int value) 
{
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode)); // 分配内存
    newNode->val = value;        // 初始化数据字段
    newNode->next = NULL;        // 初始化指针字段为NULL
    return newNode;
}


struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
    struct ListNode* r1=reverseList(l1);
    struct ListNode* r2=reverseList(l2);
    struct ListNode* r3=createNode(0);
    struct ListNode* head=r3;
    int carry = 0;
    while(l1||l2)
    {
      int n1 = (r1!=NULL) ? r1->val :0;
      int n2 = (r2!=NULL) ? r2->val :0;
      int sum = n1 + n2 + carry;
      r3->val=(sum%10);carry=sum/10;
      r3->next=createNode(carry);
      r3=r3->next;
      if(r1)
        {
          r1 = r1->next;
        }
      if(r2)
        {
          r2 = r2->next;
        }
    }
    if(carry>0) 
    {
        r3->next=createNode(carry);
    }
    
    return reverseList(head);
}

结果显示超时，请问我的代码存在什么问题？

又改了相关代码，但是WA了，请问问题出在哪？

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL, *curr = head, *next;
    while (curr != NULL) {
        next = curr->next; 
        curr->next = prev; 
        prev = curr;       
        curr = next;      
    }
    return prev; 
}
struct ListNode* createNode(int value) 
{
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode)); 
    newNode->val = value;        
    newNode->next = NULL;        
    return newNode;
}



struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) 
{
    struct ListNode *r1=reverseList(l1),*r2=reverseList(l2),*head=createNode(0);
    struct ListNode *rcrd=head;
    int carry = 0;
    while (r1 != NULL || r2 != NULL || carry > 0) { 
        int sum = (r1 != NULL) ? l1->val : 0; 
        sum += (r2 != NULL) ? r2->val : 0; 
        sum += head->val;
        carry = sum / 10; 
        head->val=sum%10;
        head->next=createNode(carry);
        r1 = r1 != NULL ? r1->next : r1; 
        r2 = r2 != NULL ? r2->next : r2; 
        head=head->next;
    }
    return reverseList(rcrd); 
}

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

根据您提供的代码和题目描述，看起来您的代码是正确的思路，反转链表，然后按位相加并保留进位。但在处理某些情况时可能会存在性能问题导致超时。主要问题在于处理空链表和最后的反转步骤上。在反转链表的过程中，你需要考虑更多的边界情况。这里有一些可能的优化和改进：

1. 避免不必要的内存分配和释放：在您的代码中，每次循环都会创建一个新的节点来存储进位值，这在某些情况下会导致大量的内存分配和释放操作，从而降低性能。可以考虑使用一个指针来追踪当前的末尾节点，然后在每次迭代时直接在末尾添加节点，这样就不需要进行额外的内存分配和释放了。这可能会改善性能并避免超时。
2. 优化反转链表操作：在反转链表时，可以考虑使用快慢指针的方法，这样可以避免遍历整个链表来反转它。当遍历链表时，可以使用一个额外的指针来追踪前一个节点，从而直接在原地进行指针交换，减少不必要的遍历操作。这也可以提高性能。

以下是一个简化的版本，使用上述优化来提高性能：

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL, *curr = head, *next;
    while (curr != NULL) {
        next = curr->next; // 保存下一个节点指针
        curr->next = prev; // 当前节点指向前一个节点
        prev = curr;       // 更新前一个节点为当前节点
        curr = next;       // 更新当前节点为下一个节点指针指向的节点
    }
    return prev; // 返回反转后的链表头节点
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode dummyHead, *tail = &dummyHead; // 使用哑节点简化处理头节点的逻辑
    int carry = 0; // 进位值
    while (l1 != NULL || l2 != NULL || carry > 0) { // 直到两个链表都为空且没有进位值为止
        int sum = (l1 != NULL) ? l1->val : 0; // 获取当前节点的值或默认为0
        sum += (l2 != NULL) ? l2->val : 0; // 获取下一个节点的值或默认为0
        sum += carry; // 加上进位值
        carry = sum / 10; // 更新进位值
        tail->next = createNode(sum % 10); // 创建新节点并连接到尾部，使用取余操作得到当前位的值
        tail = tail->next; // 更新尾部节点为刚刚创建的节点
        l1 = l1 != NULL ? l1->next : l1; // 移动到下一个节点或保持不变（根据l1是否为空）
        l2 = l2 != NULL ? l2->next : l2; // 移动到下一个节点或保持不变（根据l2是否为空）
    }
    return dummyHead.next; // 返回哑节点的下一个节点作为结果链表的头节点（去掉哑节点）
}

这些优化可能会改善您的代码性能并解决超时问题。另外，请注意在处理内存分配和释放时要小心，确保释放不再需要的内存块以避免内存泄漏问题。