NWPU 数据结构 NOJ 004 合并有序链表

题意

假设两个按元素值非递减有序排列的线性表 $A$ 和 $B$,均以单链表作为存储结构,试编写程序,将A表和B表归并成一个按元素值非递增有序排列的线性表 $C$,并要求利用原表(即 $A$ 表和 $B$ 表的)结点空间存放表 $C$。

输入

第一行输入两个正整数 $m,n\,\,(m,n\leq 100)$,用空格分开,分别表示线性表 $A$ 和 $B$ 中元素个数,其后两行分别输入单链表A和B。

解法

整体的思路是设定三个指针 run, ref, prun 用来比较 run 和 ref 指向的值,若大于则将 prun = run,run = run->nxt,找到分割位置将 prun->nxt = ref,之后更新新的 run, ref 和 prun,需要处理边界条件即 run == NULL 时的情况,方案见代码。

#include <cstdio> #include <iostream> #include <algorithm> #include <cassert> using namespace std; class pNode { public: int x; pNode* nxt; }; int n, m; void print(pNode* s) { pNode *p3 = s; while(p3 != NULL) { printf("%d ", p3->x); p3 = p3->nxt; } puts(""); } void clean(pNode* s) { if(s == NULL) return; clean(s->nxt); free(s); } int main() { // freopen("004.in", "r", stdin); cin >> n >> m; pNode* h1 = (pNode*)malloc(sizeof(pNode)); pNode* h2 = (pNode*)malloc(sizeof(pNode)); h1->nxt = h2->nxt = NULL; while(n--) { int y; cin >> y; pNode* b = h1->nxt; pNode* c = (pNode*)malloc(sizeof(pNode)); c->nxt = b; c->x = y; h1->nxt = c; } while(m--) { int y; cin >> y; pNode* b = h2->nxt; pNode* c = (pNode*)malloc(sizeof(pNode)); c->nxt = b; c->x = y; h2->nxt = c; } pNode *ref = h1->nxt; pNode *run = h2->nxt; pNode *prun = h2; bool f = 0; while(1) { while(run->x > ref->x) { // printf("ref -> x = %d\n", ref->x); // printf("run -> x = %d\n", run->x); prun = run; run = run->nxt; // printf("update run -> x = %d\n", run->x); if(run == NULL) { f = 1; break; } } if(f) { prun->nxt = ref; break; } prun->nxt = ref; prun = ref; pNode* tmp = ref->nxt; ref = run; run = tmp; if(run == NULL) { prun->nxt = ref; break; } // printf("run -> x = %d and ref -> x = %d\n", run->x, ref->x); } print(h2->nxt); clean(h1); clean(h2); return 0; }
Code language: PHP (php)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注