线性表的应用
- 链式有序表的合并
- 旋转链表
- 分隔链表
- 翻转链表
#include<iostream>
#include<cstdlib>
using namespace std;
typedef int ElemType;
typedef int Status;
typedef struct LNode{
ElemType data;
struct LNode *next;
int val;
}LNode,*LinkList;
//创建链表
void CreateList_H(LinkList &L,int n){
L=new LNode;
L->next=NULL;
cout<<"请输入"<<n<<endl;
for(int i=0;i<n;++i){
LNode*p =new LNode;
cin>>p->data;
p->next=L->next;
L->next=p;
}
}
//输出链表
void PrintList (LinkList L) {
LNode *p;
p=L->next;
while(p!=NULL) {
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
//链式有序表的合并
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)
{
LNode *pa=La->next;
LNode *pb=Lb->next;
Lc=La;
LNode *pc=Lc;
while(pa&&pb)
{
if(pa->data<=pb->data)
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa?pa:pb;
delete Lb;
}
//旋转链表
struct LNode* rotateRight(struct LNode* head,int k)
{
if(k==0||head==NULL||head->next==NULL)
return head;
int n=1;
struct LNode* tail=head;
while(tail->next !=NULL)
{
tail=tail->next;
n++;
}
int movenum=k%n;
if(movenum==0)
return head;
tail->next=head;
int addnum=n-movenum;
while(addnum--)
tail=tail->next;
struct LNode* newhead=tail->next;
tail->next=NULL;
return newhead;
}
//分隔链表
struct LNode*partition(struct LNode*head,int x)
{
struct LNode*small=(struct LNode*)malloc(sizeof(struct LNode ));
struct LNode*large=(struct LNode*)malloc(sizeof(struct LNode ));
struct LNode*pa=head;
struct LNode*pb=small;
struct LNode*pc=large;
while(pa!=NULL)
{
if(pa->val < x)
{
pb->next=pa;
pb=pb->next;
}
else{
pc->next=pa;
pc=pc->next;
}
pa=pa->next;
}
pc->next=NULL;
pb->next=large->next;
struct LNode* newhead = small->next;
return newhead;
}
//翻转链表
struct LNode* reverseKGroup(struct LNode* head,int k)
{
int x=k;
int n=0;
struct LNode* s =(struct LNode*)malloc(sizeof(struct LNode));
struct LNode* cur=s;
struct LNode* slow=head;
struct LNode* fast=NULL;
struct LNode* prev=NULL;
while(slow)
{
n++;
slow=slow->next;
}
slow=head;
n/=k;
for(int i=0;i<n;i++)
{
while(x)
{
fast=slow->next;
slow->next=prev;
prev=slow;
slow=fast;
x--;
}
cur->next=prev;
while(cur->next)
cur=cur->next;
prev=NULL;
x=k;
}
cur->next=slow;
struct LNode* newhead=s->next;
return newhead;
}
int main()
{
cout << "--- 测试 1: 合并有序链表 ---" << endl;
LinkList La, Lb, Lc;
cout << "创建链表 A (需有序): ";
CreateList_H(La, 3);
cout << "创建链表 B (需有序): ";
CreateList_H(Lb, 3);
MergeList_L(La, Lb, Lc);
cout << "合并结果: ";
PrintList(Lc);
cout << endl;// --- 测试 2: 旋转链表 ---
cout << "--- 测试 2: 旋转链表 ---" << endl;
LinkList L_rotate;
cout << "创建用于旋转的链表: ";
CreateList_H(L_rotate, 5);
int k_rot = 2;
cout << "向右旋转 " << k_rot << " 位后的结果: ";
LNode* res_rot = rotateRight(L_rotate->next, k_rot);
// 临时打印
LNode* temp = res_rot;
while(temp) { cout << temp->data << " "; temp = temp->next; }
cout << endl;
cout << endl;
// --- 测试 3: 分隔链表 ---
cout << "--- 测试 3: 分隔链表 (以 3 为界) ---" << endl;
LinkList L_part;
cout << "创建用于分隔的链表: ";
CreateList_H(L_part, 5); // 例如输入 3 1 4 1 5
LNode* res_part = partition(L_part->next, 3);
temp = res_part;
while(temp) { cout << temp->data << " "; temp = temp->next; }
cout << endl;
cout << endl;
// --- 测试 4: K 个一组翻转 ---
cout << "--- 测试 4: K 个一组翻转 (k=2) ---" << endl;
LinkList L_rev;
cout << "创建用于翻转的链表: ";
CreateList_H(L_rev, 5); // 例如输入 1 2 3 4 5
LNode* res_rev = reverseKGroup(L_rev->next, 2);
temp = res_rev;
while(temp) { cout << temp->data << " "; temp = temp->next; }
cout << endl;
return 0;
}