有序链表的合并问题

合并两个递增的单向有序链表，合并后不允许有重复的数据，不允许占用更多空间。我自己写的structure，链表是有头结点的。编译通过了，但是有问题！请问问题出在哪里，应该怎么修改呢？代码如下

//合并两个递增的有序链表，不允许有重复的数据，不允许另外占用空间。

//代码的问题如下：
//如果两个尾元素相同，最后会不断输出末尾元素。
//如果不全是尾元素的两个数相同，就判断不了while的条件，什么也不输出。。

#include <stdio.h>
#include <stdlib.h>
#define len sizeof(Num)

typedef struct Number {
    int value;
    struct Number* next;
}Num;

Num* CreatList() {
    int m;
    Num* head, *p, *p1;
    head = (Num*) malloc(len);
    head->next = NULL;
    p = head;

    printf("how many items would you like to input?\n");
    scanf("%d", &m);
    getchar();

    for (int i=0;i<m;i++) {
        p1 = (Num*) malloc(len);
        printf("Input the value:\n");
        scanf("%d", &p1->value);
        getchar();
        p->next = p1;
        p = p1;
    }
    p->next = NULL;//需要注明？
    return head;
}

void MergeLists(Num* head1, Num* head2) {
    Num* p1 = head1->next, * p2 = head2->next, * p3;
    p3 = head1;

    while (p1!=NULL&&p2!=NULL) {
        if(p1->value>p2->value) {
            p3->next = p2;
            p3 = p2;
            p2 = p2->next;
        }
        else if (p1->value<p2->value) {
            p3->next = p1;
            p3 = p1;
            p1 = p1->next;
        }
        else {
            p3->next = p1;
            p3 = p1;
            Num* temp = p2->next;
            free(p2);
            p2 = temp;
        }
    }
    p3->next = p1?p1:p2;
    free(head2);
}

void PrintList(Num* head) {
    Num* p = head->next;
    while(p) {
        printf("%d\n", p->value);
        p = p->next;
    }
}

int main() {
    Num* head1, * head2;
    printf("写入两个有序表\n");
    head1 = CreatList();
    head2 = CreatList();

    MergeLists(head1, head2);
    PrintList(head1);
    return 0;
}

5 个解决方案

#1

#include <stdio.h>
#include <stdlib.h>

#define len sizeof(Num)

typedef struct Number {
    int value;
    struct Number* next;
}Num;

Num* CreatList()
{
    int m;
    Num* head, *p, *p1;
    head = (Num*) malloc(len);
    if (!head)
        exit(0);
    head->next = NULL;
    p = head;

    printf("how many items would you like to input?\n");
    scanf("%d", &m);

    for (int i=0;i<m;i++) {
        p1 = (Num*) malloc(len);
        if (!p1)
            exit(0);
        printf("Input the value:\n");
        scanf("%d", &p1->value);
        p->next = p1;
        p = p1;
    }
    p->next = NULL;

    return head;
}

void MergeLists(Num* head1, Num* head2)
{
    Num *p1 = head1->next, *p2 = head2->next, *p3;
    p3 = head1;

    while (p1 && p2) {
        if(p1->value > p2->value) {
            p3->next = p2;
            p3 = p2;
            p2 = p2->next;
        }
        else if (p1->value < p2->value) {
            p3->next = p1;
            p3 = p1;
            p1 = p1->next;
        }
        else {
            p3->next = p1;
            p3 = p1;
            //不要忘了让p1也只想下一个节点
            p1 = p1->next;
            Num *tmp = p2->next;
            free(p2);
            p2 = tmp;
        }
    }

    while (p1) {
        p3->next = p1;
        p3 = p1;
        p1 = p1->next;
    }
    while (p2) {
        p3->next = p2;
        p3 = p2;
        p2 = p2->next;
    }
}

void PrintList(Num* head)
{
    Num* p = head->next;
    while (p) {
        printf("%d\t", p->value);
        p = p->next;
    }
    putchar(10);
}

int main()
{
    Num* head1, * head2;
    printf("写入两个有序表\n");
    head1 = CreatList();
    PrintList(head1);
    head2 = CreatList();
    PrintList(head2);

    MergeLists(head1, head2);
    printf("After merge: \n");
    PrintList(head1);
    return 0;
}

参考一下吧
两个问题：
问题1：当p1的value和p2的value相等时，将p1的节点给了p3->next，但是p1没有指向下一个节点，既没有操作p1 = p1->next；p2删除了相等的节点，指向了下一个节点；
问题2：当p1或p2为NULL时，即其中一个链表先结束时，第二个链表还没有结束，应该将剩余的节点直接链到p3上，即新的链表上。

#2

去掉getchar();这儿加getchar()没有意义。你可能考虑到，输入一个整型数时会将'\n'残留在输入缓冲里，但是'\n'是字符，不会与%d匹配的。因此不用担心这个。

#3

        else {
            p3->next = p1;
            p3 = p1;
            p1 = p1->next;      //这里少了一句，p1未指向下一节点
            Num* temp = p2->next;
            free(p2);
            p2 = temp;
        }

#4

谢谢大家，我已经找到问题了。二楼讲的第一个问题就是主要的问题，第二个问题我的程序62行写了。

#5

引用 4 楼 Lraxer 的回复:

谢谢大家，我已经找到问题了。二楼讲的第一个问题就是主要的问题，第二个问题我的程序62行写了。

看来你没有很好理解第二个问题。你有没有考虑到两个链表不一样长，或者说两个链表的长度相差多个节点，比如5个，10个节点，
如果你用下面的测试用例试试你的代码能否正常合并：
链表1:3个节点，分别1， 2， 3，链表2：5个节点，分别：2， 3， 4， 5， 6，
正确的结果合并之后应该是：1， 2， 3， 4， 5， 6
我估计用你的逻辑不是完全输出。不信的话可以试一下