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

题目

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

题目大意：

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

输入：

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

输出：

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

解析：

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

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

复杂度分析

时间复杂度：
空间复杂度：

代码

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;
}