#include
#include
#include
#define LEN sizeof(struct Nodelist)
using namespace std;
typedef struct Nodelist
{
int data;;
struct Nodelist *next;
}Nodelist;
//函数声明
void Error(char *s); //错误处理函数
Nodelist *CreatNode(void); //后插法创建单链表
Nodelist *ReverseList(Nodelist *head); //就地逆置函数
void MeryNode(Nodelist &l1, Nodelist &l2); //就地归并函数
void printNode(Nodelist L); //输出函数
//函数定义
void Error(char *s) //错误处理函数
{
cout << s << endl;
exit(1);
}
Nodelist *CreatNode(void) //后插法创建单链表
{
int i, n;
Nodelist *head, *p, *q;
p = q = NULL;
head = NULL;
cout << "请输入您要建立的链表长度:";
cin >> n;
cout << "请输入您要输入的数据:" << endl;;
for (i = 0; i
{
p = (Nodelist *)malloc(LEN);
cin >> p->data;
if (head == NULL) //单个结点
q = head = p;
else
q->next = p;
q = p;
}
p->next = NULL;
return head;
}
void printNode(Nodelist L) //将链表依次数据输出
{
Nodelist *p = &L;
while (p)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
Nodelist *ReverseList(Nodelist *head) //就地逆置函数
{
Nodelist *p, *q, *r;
p = head;
q = r = NULL;
while (p)
{
q = p->next;
p->next = r;
r = p;
p = q;
}
return r;
}
void MeryNode(Nodelist &l1, Nodelist &l2) //就地归并函数
{
Nodelist *pa, *pb, *pc, *pd;
pa = &l1;
pb = &l2;
pc = pa;
while (pa&&pb)
{
if (pa->data <= pb->data)
{
pc = pa;
pa = pa->next;
}
else
{
pd = pb->next;
pb->next = pa;
pc->next = pb;
pc = pb;
pb = pd;
}
}
if (pb!=NULL)
pc->next = pb;
}
int main() //主函数测试
{
Nodelist *head1, *head2;
head1 = CreatNode();
cout << "逆置前的链表数据：" << endl;
printNode(*head1);
Nodelist *head3 = ReverseList(head1);
cout << "逆置后的链表数据：" << endl;
printNode(*head3);
head2 = CreatNode();
cout << "逆置前的链表数据：" << endl;
printNode(*head2);
Nodelist *head4 = ReverseList(head2);
cout << "逆置后的链表数据：" << endl;
printNode(*head4);
cout << "就地归并后：" << endl;
MeryNode(*head3, *head4);
printNode(*head3);
return 0;
}
