常见算法题：单链表二路归并
浏览数：16 /
时间：2015年06月08日
题目：现有两个递增的单链表L1和L2，设计一个算法将L1与L2的所有结点归并到递增的单链表L3中。要求：空间复杂度为O(1)。
思路：本题可采用二路归并思路，但题目要求空间复杂度为O(1)，因此不能复制结点，只能破坏L1和L2将结点插入到L3中。
代码：
void Merge(LinkList &L1,LinkList &L2,LinkList &L3)
{
LinkList *p=L1.head->next, *q=L2.head->next;
LinkList *p1, *q1, *r;
L1.head->next=NULL; //将L1、L2置为空表
L2.head->next=NULL;
r=L3.head;
while(p!=NULL&&q!=NULL) //两个表均未遍历完时
{
if(p->data<q->data)
{
p1=p->next; //将L1中的结点插入L3
r->next=p;r=p;
p=p1;
}
else
{
q1=q->next; //将L2中的结点插入L3
r->next=q;r=q;
q=q1;
}
}
while(p!=NULL) //若L1未遍历完，将剩余所有结点插入到L3
{
p1=p->next;
r->next=p;r=p;
p=p1;
}
while(q!=NULL) //若L2未遍历完，将剩余所有结点插入到L3
{
q1=q->next;
r->next=q;r=q;
q=q1;
}
r->next=NULL; //将L3尾结点置为NULL
}该算法中没有新建结点，因此空间复杂度为O(1)。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
