题目
将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;
}
网友评论