ListNode *pa , *pb , *qa , *qb ;
pa=A;
pb=B ;
qa=A->next;
qb=B->next;
while ( qa && qb)
{
if ( qb->data < qa->data )
{
// 当B中的元素小于A中当前元素时，插入到它的前面
pb=qb;
qb=qb->next ;// 指向B中下一元素
pa->next=pb;
pb->next=qa;
pa=pb;
}
else if ( qb->data >= pa->data && qb->data <= qa->data)
{
// 当B中元素大于等于A中当前元素
// 且小于等于A中后一元素时，
// 将此元素插入到A的当前元素之后
pa=qa;
qa=qa->next; // 保存A的后一元素位置
pb=qb;
qb=qb->next; // 保存B的后一元素位置
pa->next=pb; //插入元素
pb->next=qa;
}
else
{
// 如果B中元素总是更大,指针移向下一个A元素
pa=qa;
qa=qa->next;
}
}
if ( qb )// 如果A表已到终端而B表还有结点未插入
{
// 将B表接到A表后面
pa->next=qb;
}
LinkList C=ReverseList ( A );// 调用前面2.8题所设计的逆置函数
return C; //返回新的单链表C, 已是递减排列
}
该算法的时间复杂度分析如下：
算法中只有一个while 循环，在这个循环中，按照最坏的情况是B元素既有插到A的最前的，也有插到最后的，也就是说需要把A中元素和B中元素全部检查比较过，这时的所费时间就是m+n. 而新链表的长度也是m+n+1 (有头结点)，这样逆置函数的执行所费时间为m+n+1.所以可得整个算法的时间复杂度为：
m+n+m+n+1=2(m+n)+1= O(m+n)
---------------------------------------------------------------------------------------------------------
为验证本题，晓津设计了一个程序，清单如下：
//ListStruct.h 将链表结构存为头文件
typedef char DataType; //假设结点的数据类型是字符型
typedef struct node { //结点类型定义
DataType data;
struct node *next;//结点的指针域
}ListNode;
typedef ListNode * LinkList;
// 以下是源文件 // 在VC++中运行通过。
#include
#include
#include "ListStruct.h"
#include
LinkList CreatList (void)
{ //用尾插法建立带头结点的单链表
char ch;
LinkList head = (LinkList)malloc(sizeof( ListNode)); //生成头结点
ListNode *s , *r;
r=head;//尾指针亦指向头结点
while ((ch=getchar())!='/n')
{
s=(ListNode *) malloc (sizeof(ListNode));
s->data=ch;
r->next=s;
r=s;
}
r->next=NULL;
return head;
}
void OutList( LinkList L)
{
ListNode *p;
p=L;
while (p->next)
{
cout << p->next->data << " " ;
p=p->next;
}
cout << endl;
}
LinkList ReverseList( LinkList head )
{
// 将head 所指的单链表逆置
ListNode *p ,*q ;//设置两个临时指针变量
if( head->next && head->next->next)//当链表不是空表或单结点时
{
p=head->next;
q=p->next;
p -> next=NULL;//将开始结点变成终端结点
while (q)
{//每次循环将后一个结点变成开始结点
p=q;
q=q->next ;
p->next = head-> next ;
head->next = p;
}
return head;
}
return head;//直接返回head
}
LinkList MergeSort ( LinkList A , LinkList B )
{
// 归并两个递增有序表为一个递减有序表
ListNode *pa , *pb , *qa , *qb ;
pa=A;
pb=B ;
qa=A->next;
qb=B->next;
while ( qa && qb)
{
if ( qb->data < qa->data )
{
// 当B中的元素小于A中当前元素时，插入到它的前面
pb=qb;
qb=qb->next ;// 指向B中下一元素
pa->next=pb;
pb->next=qa;
pa=pb;
}
else if ( qb->data >= pa->data && qb->data <= qa->data)
{
// 当B中元素大于等于A中当前元素
// 且小于等于A中后一元素时，
// 将此元素插入到A的当前元素之后
pa=qa;
qa=qa->next; // 保存A的后一元素位置
pb=qb;
qb=qb->next; // 保存B的后一元素位置
pa->next=pb; //插入元素
pb->next=qa;
}
else
{
// 如果B中元素总是更大,指针移向下一个A元素
pa=qa;
qa=qa->next;
}
}
if ( qb )// 如果A表已到终端而B表还有结点未插入
{
// 将B表接到A表后面
pa->next=qb;
}
LinkList C=ReverseList ( A );// 调用前面2.8题所设计的逆置函数
return C; //返回新的单链表C, 已是递减排列
}
void main()
{
LinkList A, B, C;
A=CreatList();
OutList (A);
B=CreatList();
OutList (B);
C=MergeSort (A ,B);
OutList (C);
}
---------------------------------------------------
--------------------------------------------------------------------------------
(答案及点评) 2.14 已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min 且小于max的结点(若表中有这样的结点)，同时释放被删结点的窨，这里min 和 max是两个给定的参数。请分析你的算法的时间复杂度。
2.14 解：
要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max和min比较，然后删除这个结点，其实因为已知其是有序链表，所以我们只要找到大于min的结点的直接前趋结点，再找到小于max的结点，然后一并把中间的全部摘掉就可以了。
算法如下：
void DeleteList ( LinkList L, DataType min , DataType max )
{
ListNode *p , *q , *h;
p=L->next;
while( p && p->data <=min )
{//找比min大的前一个元素位置
q=p;
p=p->next;
}
p=q;//保存这个元素位置
