线性表算法设计题（二）

题目

将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。

算法思想

从原有两个链表中依次摘取结点，通过更改结点的指针域来重新建立新的元素之间的线性关系，得到一个新的链表。关键点：（1）为保证新表与原表顺序相反，需要利用前插法建立单链表，而不能利用后插法；（2）当一个表到达表尾结点为空时，另一个非空表的剩余元素应该依次摘取，依次链接在Lc表的表头结点之后，而不能全部直接链接在Lc表的最后。

完整代码

#include <iostream>
#include <stdlib.h> 
using namespace std;

//将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据 

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

void ListRead(LinkList &L){
    //读取链表，即给链表添加数据 
    int length;
    LinkList  p = NULL, q;
    cout << "Input the length:";
    cin >> length;
    L = (LinkList)malloc(sizeof(struct LNode));
    L -> next = NULL;
    q = L;
    for(int i = 0; i < length; ++ i){
        p = (LinkList)malloc(sizeof(struct LNode));     //生成头结点 
        cin >> p -> data;
        q -> next = p;
        q = q -> next;
    }
    p -> next = NULL;
}

void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc){
    //将两个非递减的有序链表La和Lb合并为一个非递增的有序链表Lc 
    LinkList pa, pb, pc, q;                        
    pa = La -> next;                           //pa是链表La的工作指针，初始化为首元结点 
    pb = Lb -> next;                           //pb是链表Lb的工作指针，初始化为首元结点  
    Lc = pc = La;                              //用La的头结点作为Lc的头结点 
    Lc -> next =NULL;
    while(pa || pb){                           //只要有一个表未到达表尾结点，用q指向待摘取的元素 
        if(! pa){                              //La表为空，用q指向pb，pb指针后移 
            q = pb;
            pb = pb -> next;
        }
        else if(! pb){                         //Lb表为空，用q指向pa,pa指针后移 
            q = pa;
            pa = pa -> next;
        }
        else if(pa -> data <= pb -> data){     //取较小者La中的元素，用q指向pa，pa指针后移 
            q = pa;
            pa = pa -> next;
        }
        else{                                  //取较小者La中的元素，用q指向pa，pa指针后移
            q = pb;
            pb = pb -> next;
        }
        q -> next = Lc -> next;
        Lc -> next = q;                        //将q指向的结点插在Lc的表头结点之后 
    }
    delete Lb;                                 //释放Lb的头结点 
}

void ListPrint(LinkList L){
    //打印链表 
    LNode *p;
    p = L -> next;
    if(L -> next == NULL){
        cout << "NULL" << endl;
    }
    while(p){
        cout << p -> data << "\t";
        p = p -> next;
    }
    cout << endl; 
}

int main(){
    LinkList La, Lb, Lc;
    ListRead(La);
    ListRead(Lb);
    MergeList(La,Lb,Lc);
    cout << "合并之后的链表为：" << endl; 
    ListPrint(Lc); 
    return 0;
}

结果显示

5`G65R~`I_OR3)UP(0~FZ2D.png