线性表的应用

链式有序表的合并旋转链表分隔链表翻转链表#includeiostream#includecstdlibusing 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){Lnew LNode;L-nextNULL;cout请输入nendl;for(int i0;in;i){LNode*p new LNode;cinp-data;p-nextL-next;L-nextp;}}//输出链表void PrintList (LinkList L) {LNode *p;pL-next;while(p!NULL) {coutp-data ;pp-next;}coutendl;}//链式有序表的合并void MergeList_L(LinkList La,LinkList Lb,LinkList Lc){LNode *paLa-next;LNode *pbLb-next;LcLa;LNode *pcLc;while(papb){if(pa-datapb-data){pc-nextpa;pcpa;papa-next;}else{pc-nextpb;pcpb;pbpb-next;}}pc-nextpa?pa:pb;delete Lb;}//旋转链表struct LNode* rotateRight(struct LNode* head,int k){if(k0||headNULL||head-nextNULL)return head;int n1;struct LNode* tailhead;while(tail-next !NULL){tailtail-next;n;}int movenumk%n;if(movenum0)return head;tail-nexthead;int addnumn-movenum;while(addnum--)tailtail-next;struct LNode* newheadtail-next;tail-nextNULL;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*pahead;struct LNode*pbsmall;struct LNode*pclarge;while(pa!NULL){if(pa-val x){pb-nextpa;pbpb-next;}else{pc-nextpa;pcpc-next;}papa-next;}pc-nextNULL;pb-nextlarge-next;struct LNode* newhead small-next;return newhead;}//翻转链表struct LNode* reverseKGroup(struct LNode* head,int k){int xk;int n0;struct LNode* s (struct LNode*)malloc(sizeof(struct LNode));struct LNode* curs;struct LNode* slowhead;struct LNode* fastNULL;struct LNode* prevNULL;while(slow){n;slowslow-next;}slowhead;n/k;for(int i0;in;i){while(x){fastslow-next;slow-nextprev;prevslow;slowfast;x--;}cur-nextprev;while(cur-next)curcur-next;prevNULL;xk;}cur-nextslow;struct LNode* newheads-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 5LNode* 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 个一组翻转 (k2) --- endl;LinkList L_rev;cout 创建用于翻转的链表: ;CreateList_H(L_rev, 5); // 例如输入 1 2 3 4 5LNode* res_rev reverseKGroup(L_rev-next, 2);temp res_rev;while(temp) { cout temp-data ; temp temp-next; }cout endl;return 0;}