编程论坛 → C++教室

链表排序问题

逆水寒刘发布于 2013-03-28 12:58， 484 次点击

我想将两个非递减的链表合并成一个非递增的新链表；但是出了点问题，请大家看看；
struct Node *MergeLisk(struct Node *head1,struct Node *head2)
{
    struct Node *p1;/*链表一中的工作指针*/
    struct Node *q1;/*链表二中的工作指针*/
    //struct Node *t1;/*链表三中的工作指针*/
    struct Node *p2;/*链表一中用来记录p1下一个结点*/
    struct Node *q2;/*链表二中用来记录q1的下一个结点*/
    struct Node *head3;
    head3=head1;
    p1=head1->next;
    q1=head2->next;
    head3->next=NULL;
    while(p1!=NULL&&q1!=NULL)
    {
        if(p1->iNum<=q1->iNum)
        {
            p2=p1->next ;
            p1->next =head3->next ;
            head3->next =p1;
            p1=p2;
        }
        else{
            q2=q1->next ;
            q1->next=head3->next ;
            head3->next=q1;
            q1=q2;
        }
}
    if(p1==NULL)/*

判断如果有一个链表为空了，就将另一个表的元素头插进*但问题就是运行结果出现了非预料的情况
    {
            q2=q1->next;
            q1->next=head3->next;
            head3->next=q1;
            q1=q2;

    }
     if(q1==NULL)
    {
               p2=p1->next ;
            p1->next=head3->next ;
            head3->next=p1;
            p1=p2;
    }
     free(head2);

4 回复

#2

锋了2013-03-29 11:00

这个有点复杂，得花的时间才能找的出的，等看我还是谁什么时候有时间先了

#3

gfchen18192013-03-29 11:47

感觉你一直操作的是head3->next，struct Node *MergeLisk(struct Node *head1,struct Node *head2)
{
     struct Node *p1;/*链表一中的工作指针*/
     struct Node *q1;/*链表二中的工作指针*/
     //struct Node *t1;/*链表三中的工作指针*/
     struct Node *p2;/*链表一中用来记录p1下一个结点*/
     struct Node *q2;/*链表二中用来记录q1的下一个结点*/
     struct Node *head3,h;
     head3=head1;
     p1=head1->next;
     q1=head2->next;
     h->next=NULL;
     while(p1!=NULL&&q1!=NULL)
     {
         if(p1->iNum<=q1->iNum)
         {
             h=p1;
             p1=p1->next;
         }
         else{
             h=q1;
             q1=q1->next;
         }
         h->next = head1->next;
         head1->next = h;
}
     if(p1==NULL)//判断如果有一个链表为空了，就将另一个表的元素头插进*但问题就是运行结果出现了非预料的情况
     {
             h=q1;
             q1=q1->next;
             h->next=head1->next;
             head1->next=h;
    }
      if(q1==NULL)
     {
            h=p1;
            p1=pq->next;
            h->next=head1->next;
            head1->next = h;
     }
     return head1;//这个head1是不能return的，我这样写是错误的，要想return，最好把head1放在参数中，
}

#4

gfchen18192013-03-29 11:49

失误，错了，把head1全改head3struct Node *MergeLisk(struct Node *head1,struct Node *head2)
{
     struct Node *p1;/*链表一中的工作指针*/
     struct Node *q1;/*链表二中的工作指针*/
     //struct Node *t1;/*链表三中的工作指针*/
     struct Node *p2;/*链表一中用来记录p1下一个结点*/
     struct Node *q2;/*链表二中用来记录q1的下一个结点*/
     struct Node *head3,h;
     head3=h=head1;
     p1=head1->next;
     q1=head2->next;
     h->next=NULL;
     while(p1!=NULL&&q1!=NULL)
     {
         if(p1->iNum<=q1->iNum)
         {
             h=p1;
             p1=p1->next;
         }
         else{
             h=q1;
             q1=q1->next;
         }
         h->next = head3->next;
         head3->next = h;
}
     if(p1==NULL)//判断如果有一个链表为空了，就将另一个表的元素头插进*但问题就是运行结果出现了非预料的情况
     {
             h=q1;
             q1=q1->next;
             h->next=head3->next;
             head3->next=h;
    }
      if(q1==NULL)
     {
            h=p1;
            p1=p1->next;
            h->next=head3->next;
            head3->next = h;
     }
     return head3;//这个head3是不能return的，我这样写是错误的，要想return，最好把head3放在参数中，
}

#5

逆水寒刘2013-03-29 13:08

回复 4楼 gfchen1819

先谢了！4楼！

1