两个有序链表交集函数无法进入for循环的问题排查

你遇到的核心问题是**createlist函数的逻辑错误导致head1实际为NULL（或无效野指针）**，即使你认为它不为空，因此无法进入intersectlist的外层for循环。

createlist函数的关键错误 #

1. 冗余内存分配与泄漏：在创建第一个节点时，你连续两次调用malloc，然后将*p覆盖为str，导致第一次分配的内存完全泄漏，且完全无意义：

*p = (struct node*)malloc(sizeof(struct node)); // 这块内存直接被丢弃
str = (struct node*)malloc(sizeof(struct node));
*p = str;

2. 链表构建逻辑混乱：错误的内存分配逻辑可能导致*p（即head1）指向无效内存，或者在某些场景下被意外置空，最终传递给intersectlist的p1实际为NULL。

修正后的createlist函数 #

以下是修复后的链表创建函数，确保正确构建有序链表：

void createlist(struct node **p , int n)
{
    int i=0;
    struct node *str = NULL;

    for(i=0;i<n;i++)
    {
        struct node *new_node = (struct node*)malloc(sizeof(struct node));
        if(new_node == NULL) {
            printf("内存分配失败\n");
            exit(1);
        }
        getval(new_node);

        if(*p == NULL) {
            *p = new_node;
            str = new_node;
        } else {
            str->next = new_node;
            str = new_node;
        }
    }
    // 最后一个节点的next已经在getval中设为NULL，无需额外操作
}

intersectlist函数的额外问题 #

除了上述核心问题，你的交集函数还有两处逻辑错误：

1. 新增节点时赋值错误：在else分支中，你错误地修改了当前节点的val，而非新创建的节点：

// 错误写法
str->next = (struct node*)malloc(sizeof(struct node));
str->val = p3->val; // 修改的是当前节点的val，不是新节点
str=str->next;
// 正确写法
str->next = (struct node*)malloc(sizeof(struct node));
str->next->val = p3->val;
str->next->next = NULL;
str = str->next;

2. 效率低下的嵌套循环：由于是有序链表，你可以用更高效的双指针法替代嵌套循环，同时避免重复元素：

void intersectlist(struct node *p1 , struct node *p2 )
{
    struct node *head3 = NULL;
    struct node *str = NULL;

    while(p1 != NULL && p2 != NULL) {
        if(p1->val == p2->val) {
            struct node *new_node = (struct node*)malloc(sizeof(struct node));
            new_node->val = p1->val;
            new_node->next = NULL;

            if(head3 == NULL) {
                head3 = new_node;
                str = new_node;
            } else {
                str->next = new_node;
                str = new_node;
            }
            // 跳过重复元素（按需保留）
            p1 = p1->next;
            p2 = p2->next;
        } else if(p1->val < p2->val) {
            p1 = p1->next;
        } else {
            p2 = p2->next;
        }
    }

    // 打印结果
    struct node *p = head3;
    while(p != NULL) {
        printf("%d ", p->val);
        p = p->next;
    }
}

总结 #

先修复createlist函数的内存分配逻辑，确保head1和head2正确指向有效的链表头节点，之后intersectlist的外层循环就能正常执行。同时优化交集函数的实现，利用有序链表的特性提升效率。

内容的提问来源于stack exchange，提问作者loop