国内股票量化交易接口-题02线性结构1 两个有序链表序列的合并

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。

函数接口定义：

其中List结构定义如下：

typedefstructNodePtrToNode;structNode{ElementTypeData;/存储结点数据/PtrToNodeNext;/指向下一个结点的指针/};typedefPtrToNodeList;/定义单链表类型*/

L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */

List Merge( List L1, List L2 );

int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

输出样例：

L1链：L1指针指向头结点，temp1指针用来依次指向头结点后的带数据的结点。L2链：L2指针指向头结点，temp2指针用来依次指向头结点后的带数据的结点。L链：用来连接生成新的合并链，temp指针先指向头结点，每合并一个结点就往后指向最后有个结点。通过指针对节点进行操作：指针temp1和temp2各自指向的结点进行对比。将对比后小的那个结点的后一个结点作为它所在链的第一个带数据的结点，也就是将该链的头结点指向小结点的后一个结点。对比完通过指针temp操作L链连接比较小的那个结点④指针temp、temp1和temp需变动的指针为L链的和小的结点所在的链的指针，往后指向下一个结点。。

当有个链遍历完，则该链只剩下头结点，则该链上游动的指针会指向头结点所指的地址为NULL。退出比较，再查看是否还有不为空的另外的链，有不为空的链就把它剩下的部分接到L链后。

补充的代码

List Merge(List L1,List L2)
{
    //取L1的第一个整数，通过L1指针指向的头结点的Next来取数List L1->Next
    //创建L的头结点
    List L = (List)malloc(sizeof(struct Node));
    //创建temp1、temp2和temp为临时指针来遍历结点
    List temp,temp1,temp2;
    //temp指向L的头结点
    temp = L;
    //temp1和temp2指向L1和L2的第一个结点（非头结点）
    temp1 = L1->Next;
    temp2 = L2->Next;
    //L1和L2链都不为空（除头结点）
    while(temp1!=NULL&&temp2!=NULL)
    {
        if(temp1->Data<temp2->Data){
            L1->Next = temp1->Next;//L1头结点指向该最小值的后一个结点
            temp->Next = temp1;//L链加入该最小值结点
            temp = temp1;
            temp1 = L1->Next;
        }else{
            L2->Next = temp2->Next;
            temp->Next = temp2;
            temp = temp2;
            temp2 = L2->Next;
        }
    }
    if(temp1==NULL&&temp2!=NULL){
        temp->Next = temp2;
        L2->Next = NULL;
    }else if(temp2==NULL&&temp1!=NULL){
        temp->Next = temp1;
        L1->Next = NULL;
    }
//     free(temp1);//这三个free的代码都不能加，加了就出错。
//     free(temp2);
//     free(temp);
    return L;
}

注意不要在后面free掉指针，会出现这些错误：free;

free(temp1);
//     free(temp2);
//     free(temp);

free;

//      free(temp1);
     free(temp2);
//     free(temp);

free;

//      free(temp1);
//      free(temp2);
     free(temp);

文章为作者独立观点，不代表股票程序化软件自动交易接口观点