将两个非递减次序排列的单链表归并为一个非递增次序排列的单链表，并计算表长。要求利用原来两个单链表的结点存放归并后的单链表。

Question

将两个非递减次序排列的单链表归并为一个非递增次序排列的单链表，并计算表长。要求利用原来两个单链表的结点存放归并后的单链表。
请用C++编写程序

Answer 1

代码如下，如有帮助，请帮忙采纳一下，谢谢。

#include <iostream>
using namespace std;

struct StNode 
{
    int data;
    struct StNode* next;
};

//创建节点
StNode* CreateNode(int d)
{
    StNode* node = new StNode;
    node->data = d;
    node->next = 0;
    return node;
}
//创建链表
StNode* CreateList()
{
    StNode* head,*p,*t;
    head = 0;
    p = head;
    t = head;
    int data;
    //cout << "请输入链表中各节点的值:" ;
    while(1)
    {
        cin >> data;
        t = CreateNode(data);
        if(head ==0)
        {
            head = t;
            p = head;
        }
        else
        {
            p->next = t;
            p = t;
        }

        if (cin.get() == '\n') 
            break;

    }
    return head;
}
//打印链表
void Display(StNode* head)
{
    cout << "打印链表：" << endl;
    while(head)
    {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

//链表逆序
StNode* Reverse(StNode* head)
{
    StNode *next = NULL;
    StNode *prev = NULL;
    while (head) {
        next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}
//计算表长
int Length(StNode* head)
{
    int len = 0;
    while(head)
    {
        len++;
        head = head->next;
    }
    return len;
}

//合并链表
StNode* Merge(StNode* h1,StNode* h2)
{
    //因为原来的链表是非递减次序，所以需要先逆序
    StNode* list1 = Reverse(h1);
    StNode* list2 = Reverse(h2);


    //合并为非递增序列（按递减序列处理）
    StNode* head = 0;
    StNode* tmp = 0;
    StNode* pps = 0;

    if(list1->data >= list2->data)
    {
        head = list1;
        list1 = list1->next;
    }else 
    {
        head = list2;
        list2 = list2->next;
    }
    pps = head;

    while(list1 && list2 )
    {
        if(list1->data >= list2->data)
        {
            pps->next = list1;
            pps = list1;
            list1 = list1->next;
        }else 
        {
            pps->next = list2;
            pps = list2;
            list2 = list2->next;
        }
    }
    while(list1)
    {
        pps->next = list1;
        pps = list1;
        list1 = list1->next;
    }

    while(list2)
    {
        pps->next = list2;
        pps = list2;
        list2 = list2->next;
    }
    pps->next = 0;


    return head;
}


int main()
{
    //创建两个链表：输入非递减数列（即递增序列，如1 2 3 4 5或者1 2 2 3 4 5，回车符结束）
    cout << "创建非递减链表1：" << endl;
    StNode* list1 = CreateList();
    cout << "创建非递减链表2：" << endl;
    StNode* list2 = CreateList();
    //合并
    StNode* hh = Merge(list1,list2);
    //计算长度
    int len = Length(hh);
    cout << "合并后的链表长度：" << len << endl;
    //打印链表
    Display(hh);
    return 0;
}