论坛 › C\C++交流 › 合并两个有序链表，有bug

020730 发表于 2022-10-3 23:32:31

合并两个有序链表，有bug

问题：有时候能全部合并到一个链表中，有时候会丢掉重复的一些。不知道哪里出错了{:10_266:}
成功的情况


不成功的情况


这一块是合并两个有序链表的函数
LinkList* Combine(LinkList **La,LinkList **Lb){
        LinkList *cura = *La;
        LinkList *curb = *Lb;
        LinkList *prevNode = NULL;
        LinkList *nextNode = NULL;
       
        while(cura!=NULL&&curb!=NULL){
       
                if((cura->data)<=(curb->data)){
                       
                        prevNode = cura;
                        cura = cura->next;
               
                }else{
                       
                        nextNode = curb->next;
                        prevNode->next = curb;
                       
                        curb->next = cura;
                        curb = nextNode;
                       
                }
        }
       
        if(cura==NULL){
                printf("La为空\n");
                prevNode->next = curb;//为什么cura = curb 不可以？
               
        }else{
                printf("Lb为空\n");
        }
        return *La;
}
这个是用主函数调用
int main(){
       
        LinkList *La = NULL;//初始化
        LinkList *Lb = NULL;
        ElemType e;//插入的元素的值
        int i;
        int num1=5,num2=8;//链表中元素的个数
        //链表La
        for(i=0;i<num1;i++){
                printf("请输入赋给链表La中第%d个元素的值：",(i+1));
                scanf("%d",&e);
                TailInsert(&La,e);
        }
        printf("链表La: ");
        PrintLinkList(La);
        //链表Lb
        for(i=0;i<num2;i++){
                printf("请输入赋给链表Lb中第%d个元素的值：",(i+1));
                scanf("%d",&e);
                TailInsert(&Lb,e);
        }
        printf("链表Lb: ");
        PrintLinkList(Lb);
       
        La = Combine(&La,&Lb);
        printf("合并后的链表: ");
        PrintLinkList(La);
        int len = LengthLinkList(La);
        printf("链表长度为%d\n",len);
       
        return 0;
}

jhq999 发表于 2022-10-4 07:41:12

本帖最后由 jhq999 于 2022-10-4 12:40 编辑

LinkList* Combine(LinkList **La,LinkList **Lb){
      LinkList *cura = *La;
      LinkList *curb = *Lb;
      LinkList *prevNode = NULL;
      LinkList *nextNode = NULL;
      
      while(cura!=NULL&&curb!=NULL){
         
                if((cura->data)<=(curb->data)){///////如果不想去重<=改成<
                        
                        prevNode = cura;
                        cura = cura->next;
               
                }else{
                        
                        nextNode = curb->next;
                        prevNode->next = curb;
                        
                        curb->next = cura;
                        curb = nextNode;
                        
                }
      }
      
      if(cura==NULL){
                printf("La为空\n");
                while(curb&&curb->data<=prevNode->data)
                        curb=curb->next;//////////如果去重添加这个就把cura最后一个和curb去重
                prevNode->next = curb;//为什么cura = curb 不可以？/////cura=NULL和prevNode->next =NULL，虽然值一样，但没有关系，prevNode->next不指向cura
               
      }else{
                printf("Lb为空\n");
      }
      return *La;
}

jackz007 发表于 2022-10-4 13:41:39

本帖最后由 jackz007 于 2022-10-4 21:10 编辑

      此函数可以兼容多个等值节点
LinkList * Combine(LinkList ** La , LinkList ** Lb)
{
      LinkList * h , * p1 , * p2 , * p3                                       ;
      p1 = ((* La) -> data < (* Lb) -> data) ? * La : * Lb                      ;
      p2 = ((* La) -> data < (* Lb) -> data) ? * Lb : * La                      ;
      for(h = p1 ; p1 && p2 ;) {
                for(; p1 && p1 -> data <= p2 -> data ; p3 = p1 , p1 = p3 -> next) ;
                p3 -> next = p2                                                   ;
                p2 = p1                                                         ;
                p1 = p3                                                         ;
      }
      * La = h                                                                  ;
      return h                                                                  ;
}

查看完整版本: 合并两个有序链表，有bug