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)