美文网首页
【算法题】1.合并两个递增的有序链表

【算法题】1.合并两个递增的有序链表

作者: _涼城 | 来源:发表于2020-04-13 11:25 被阅读0次
    题目

    将2个递增的有序链表合并为一个链表的有序链表; 要求结果链表仍然使⽤用两个链表的存储空间,不另外占用其他的存储空间. 表中不允许有重复的数据。

    题目大意:

    合并两个有序链表,附加条件:不使用任何额外开辟的空间,去除重复结点。

    输入:

    2->4->6->8,3->6->9

    输出:

    2->3->4->6->8->9

    解析:

    迭代法,不使用任何额外开辟的空间,会破坏原有链表结构。去除重复结点,只保留其中一个释放掉另外一个相同结点的空间。

    1. 维护一个新的 p3指针,指向l1的头结点,两个临时指针p1p2指向 l1l2链表。
    2. 取较小者的结点接在p3的结点后面,同时将较小者指针向后移一个。
    3. 若两者相同,取其中一个接在p3的结点后面,释放另外一个相同结点,同时将两个指针向后移一个,直到p1p2为空。
    4. 若有非空指针拼接在p3的结点后面。最后释放l2的头结点。
    复杂度分析

    时间复杂度:O(n)
    空间复杂度:O(1)

    代码
    LinkList mergeTwoLists(LinkList *l1, LinkList *l2){
      
        if (l1 == NULL)
        {    
         return *l2;
        }
        if (l2 == NULL)
        {
         return *l1;
        }
        
    
        ListNode *p1 = (*l1)->next;
        ListNode *p2 = (*l2)->next;
        ListNode *result = (*l1);
        ListNode *p3 = (*l1);
       
        while(p1!= NULL && p2 != NULL){
          
          int pVal = p1->data;
          int p2Val = p2->data;
          printf("p---%d,q---%d\n", pVal,p2Val);
           if (pVal > p2Val)
           {
    
               p3->next = p2;
               p3 = p2;
               p2 = p2->next;
           }else if (pVal < p2Val)
           {
               p3->next = p1;
              p3 = p1;
              p1 = p1->next;
           }else{
              p3->next = p1;
              p3 = p1;
              p1 = p1->next;
               ListNode *temp = p2;
              p2 = p2->next;
              free(temp);
           }
          
        }
        if (p2)
        {
           p3->next = p2;
        }else if (p1)
        {
           p3->next = p1;
        }
        free(*l2);
     return result;
    }
    

    相关文章

      网友评论

          本文标题:【算法题】1.合并两个递增的有序链表

          本文链接:https://www.haomeiwen.com/subject/rbhgmhtx.html