//将两个递增的有序链表合并为一个递增的有序链表。
//要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中不允许有重复的数据。
#include<iostream>
#include<cstdlib>
using namespace std;
#define OK 1
#define ERROR 0
typedef int Elemtype;
typedef int Status;
typedef struct LNode
{
Elemtype data;
struct LNode* next;
}LNode, * Linklist;
Status MergerList1(Linklist& La, Linklist& Lb, Linklist& Lc)
{
Lc = La;//La的头节点赋给Lc
LNode* pa, * pb, * pc, * q;
pa = La->next, pb = Lb->next;//pa为La的首元结点，pb为Lb的首元结点
pc = Lc;//pc指向Lc的头节点
while (pa && pb)
{
if (pa->data < pb->data)//取小的值
{
pc->next = pa;//链接在pc后面
pc = pa;
pa = pa->next;//pa指针后移
}
if (pa->data > pb->data)
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
if (pa->data == pb->data)//相等取La的元素，删去Lb的元素
{
pc->next = pa;
pc = pa;
pc = pa->next;
q = pb->next;
delete pb;
pb = q;
}
}
pc->next = pa ? pa : pb;//剩余段
delete Lb;
return OK;
}
//将两个非递减的有序链表合并为一个非递增的有序链表。
//要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。
Status MergerList2(Linklist& La, Linklist& Lb, Linklist& Lc)
{
Lc = La;//La的头节点赋给Lc
LNode* pa, * pb, * pc, * q;
pa = La->next, pb = Lb->next;//pa为La的首元结点，pb为Lb的首元结点
pc = Lc;//pc指向Lc的头节点
while (pa && pb)
{
if (pa->data <= pb->data)//取小的值
{
pc->next = pa;//链接在pc后面
pc = pa;
pa = pa->next;//pa指针后移
}
else
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb;
delete Lb;
return OK;
}
//已知两个链表A和B分别表示两个集合，其元素递增排列。请设计一个算法，用于求出A与B的交集，并将结果存放在A链表中
Status MergerList3(Linklist& La, Linklist& Lb, Linklist& Lc)
{
Lc = La;//La的头节点赋给Lc
LNode* pa, * pb, * pc, * q;
pa = La->next, pb = Lb->next;//pa为La的首元结点，pb为Lb的首元结点
pc = Lc;//pc指向Lc的头节点
while (pa && pb)
{
if (pa->data < pb->data)
{
q = pa;
pa = pa->next;
delete q;
}
if (pa->data > pb->data)
{
q = pb;
pb = pb->next;
delete q;
}
if (pa->data == pb->data)
{
pc->next = pa;
pc = pa;
pa = pa->next;
q = pb->next;
delete q;
pb = q;
}
}
while (pa)
{
q = pa;
pa = pa->next;
delete q;
}
while (pb)
{
q = pb;
pb = pb->next;
delete q;
}
pc->next = NULL;
delete Lb;
return OK;
}
//已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B的差集
//(仅由在A中出现而不在B中出现的元素所构成的集合)，并将结果以同样的形式存储，同时返回该集合的元素个数。
Status MergerList4(Linklist& La, Linklist& Lb)
{
int n = 0;
LNode* pa, * pb, * pre, * q;
pa = La->next, pb = Lb->next;//pa为La的首元结点，pb为Lb的首元结点
pre = La;//pa所指的前驱节点
while (pa && pb)
{
if (pa->data < pb->data)
{
pre = pa;
pa = pa->next;
n++;
}
if (pa->data > pb->data)
{
pb = pb->next;
}
if (pa->data = pb->data)
{
pre->next = pa->next;
q = pa;
pa = pa->next;
delete pa;
pa = q;
}
}
return n;
}
//设计算法将一个带头节点的单链表A分解为两个具有相同结构的链表B和C，其中B表的节点为A表中值小于0的节点，
//而C表的节点为A表中值大于0的节点(链表A中的元素为非零整数，要求B、C表利用A表的节点)。
Status MergerList5(Linklist A)
{
Linklist B, C;
B = A;
B->next = NULL;
C = new LNode;
C->next = NULL;
LNode* p,* r;
p = A->next;//p为A的首元结点
while (p)
{
r = p->next;//r为p的后继结点
if (p->data < 0)
{
p->next = B->next;
B->next = p;//前插
}
else
{
p->next = C->next;
C->next = p;//前插
}
p = r;
}
return OK;
}
//设计一个算法，通过一趟遍历确定长度为n的单链表中值最大的节点。
Status MaxList(Linklist L)
{
if (L->next = NULL) return ERROR;
LNode* pmax, * p;
pmax = L->next;//假设首元结点是值最大节点
p = L->next->next;//p指向首元结点的后继结点
while (p)
{
if (p->data > pmax->data)
{
pmax = p;
}
p = p->next;//遍历
}
return pmax->data;
}
//设计一个算法，将链表中所有节点的链接方向“原地”逆转，即要求仅利用原表的存储空间，
//换句话说，要求算法的空间复杂度为O(1)。逆序
Status Inverlist(Linklist& L)
{
if (L->next = NULL) return ERROR;
LNode* p, * q;
p = L->next;
L->next = NULL;
while (p)
{
q = p->next;//q指向p的后继结点
p->next = L->next;
L->next = p;
p = q;
}
return OK;
}
//设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素
//(mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同)。
Status Deletlist(Linklist& L, int mink, int maxk)
{
if (L->next = NULL) return ERROR;
LNode* p, * q, * pre, * s;
p = L->next;
pre = L;
while (p && p->data <= mink)
{
pre = p; p = p->next;
}
while (p && p->data < maxk)
{
q = pre->next; pre->next = p;
}
while (q != p)
{
s = q->next;
delete q;
q = s;
}
return OK;
}