题目
将2个递增的有序链表合并为一个链表的有序链表; 要求结果链表仍然使⽤用两个链表的存储空间,不另外占用其他的存储空间. 表中不允许有重复的数据。
题目大意：
合并两个有序链表，附加条件：不使用任何额外开辟的空间,去除重复结点。
输入：
2->4->6->8,3->6->9
输出：
2->3->4->6->8->9
解析：
迭代法，不使用任何额外开辟的空间,会破坏原有链表结构。去除重复结点，只保留其中一个释放掉另外一个相同结点的空间。
- 维护一个新的
p3指针,指向l1的头结点，两个临时指针p1与p2指向l1与l2链表。 - 取较小者的结点接在
p3的结点后面，同时将较小者指针向后移一个。 - 若两者相同，取其中一个接在
p3的结点后面，释放另外一个相同结点，同时将两个指针向后移一个，直到p1或p2为空。 - 若有非空指针拼接在
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;
}
