为什么我这两个有序链表不能合并为一个？

Question

 #include<stdio.h>
#include<stdlib.h>
struct stu
{
    int num;
    struct stu *next;
};
struct stu *creat()
{
//建立一个链表
    int n;
    struct stu *p1,*p2,*head;
    scanf("%d",&n);
    p1=head=(struct stu *)malloc(sizeof (struct stu));
    p1->next=NULL;
    for(int i=0;i<n;i++)
    {
        p2=(struct stu *)malloc(sizeof(struct stu));
        p2->next=NULL;
        scanf("%d",&p2->num);
        getchar();
        p1->next=p2;
        p1=p2;
    }
    p1->next=NULL;
    return head;
}
int main()
{
    struct stu *p1=NULL,*pt_a=NULL,*pt_b=NULL,*ptemp=NULL,*a=NULL,*b=NULL,*ptem=NULL,*h=NULL;
    struct stu *head=NULL;
    //新链表的表头
    a=creat();  pt_a=a;
    b=creat();  pt_b=b;
    h=a;   //head=pt_a;
//  p1=head;
     p1=h;
    while (pt_a->next&&pt_b->next)
    {
    //判断一个链表是否遍历到结尾
        if (pt_a->next->num>pt_b->next->num)
        {
            printf("\npt_a->next->num=%d,pt_b->next->num=%d\n",pt_a->next->num,pt_b->next->num);
            ptem=pt_a->next;
//先把pt_a->next这个地址保留下来
            ptemp=pt_b->next;
            pt_b=pt_b->next;
            p1->next=ptemp;
            p1=ptemp;
            pt_a->next=ptem;
            continue;
        }
        if (pt_a->next->num<=pt_b->next->num)
        {
                printf("\npt_a->next->num=%d,pt_b->next->num=%d\n",pt_a->next->num,pt_b->next->num);
                ptem=pt_b->next;
          ptemp=pt_a->next;
          pt_a=pt_a->next;
            p1->next=ptemp;
           p1=ptemp;
            pt_b->next=ptem;
            continue;
        }



    }

    while (pt_a->next||pt_b->next)
    {
        if  (pt_a->next)
        {
            ptem=pt_b->next;
            ptemp=pt_a->next;
            pt_a=pt_a->next;
            p1->next=ptemp;
            p1=ptemp;
            pt_b->next=ptem;
            continue;
        }

        if (pt_b->next)
        {
            ptem=pt_a->next;
            ptemp=pt_b->next;
            pt_b=pt_b->next;
            p1->next=ptemp;
            p1=ptemp;
            pt_a->next=ptem;
            continue;
        }
    }
    p1->next=NULL;
    printf("\n");

    p1=h->next;
     while (p1!=NULL) 
     {
        printf("%5d",p1->num);
         p1=p1->next; 
     }

     return 0;

}

Answer 1

从你的代码可以看出，你已经意识到操作p1 -> next实质上会导致两个旧链表无法访问，所以用了ptem来存储，并在执行操作后将pt_a或者pt_b的next指向ptem,但是有一个问题，在pt_a->next=ptem;这句代码之前，有两句关键代码p1->next=ptemp;和p1=ptemp; 想一下如果一开始p1和pt_a指向同一节点，然后p1->next指向了ptemp, 也就是将pt_a -> next指向了ptemp，然后将p1指向ptemp，但别忘了pt_a仍指向开始的节点，随后的pt_a -> next = ptem实质上干的事情就是将一开始p1指向的节点的next指针指向ptem（也就是a链表上该节点的下一个节点），这也就意味着p1->next = ptemp;这一操作被覆盖了，也就无效了。而这一情况不断出现，就产生了图中的结果，只有其中一条链表的元素加入了新链表。
另外，其实执行完第一个循环，直接将p1->next指向剩余的一条链表就行了，如果两条链表均为空了，则指向NULL。

pt_a = pt_a -> next;
     pt_b = pt_b -> next;
     while(pt_a && pt_b){
         if(pt_a->num > pt_b->num){
             ptemp = pt_b;
             pt_b = pt_b -> next;
             p1 -> next = ptemp;
             p1 = ptemp;
         }
         else{
             ptemp = pt_a;
             pt_a = pt_a -> next;
             p1 -> next = ptemp;
             p1 = ptemp;
         }
     }

     if(pt_a)
         p1 -> next = pt_a;
     else if(pt_b)
         p1 -> next = pt_b;
            else
                p1 -> next = NULL;