数据结构上机实践课程(2018年秋)10月机考

E. 有序环形链表的合并

单点时限: 2.0 sec

内存限制: 512 MB

现在给你两个有序的环形单向链表的头指针,这个头指针分别指向两个链表的表头结点(不存放有效数据),表头结点的下一个结点存储着第一个有效数据,因为是环形链表,所以最后一个结点指回表头结点。

下面要求你完成一个函数的定义,实现两个有序的环形单向链表的合并,并且合并之后的环形链表仍是有序的。

(有序均指升序)

函数的声明如下:

/*
 * 有序环形单向链表的合并
 * @param head1,head2 头指针,分别指向两个链表的表头结点
 * @return 返回合并后的链表的头指针,这个头指针指向合并后的链表的表头结点
 */
NODE* merge2CircularLinkedList(NODE* head1, NODE* head2)

链表结点是一个结构体:

typedef struct node {
    int data;
    // 其他数据域成员
    struct node* next;
} NODE;

除了一个整型的数据data之外,链表结点还有若干其他成员,但是你不需要也不应该去在意他们。

你只需要通过完成两个链表的合并,返回合并后的头指针即可。

结构体中的next是指向下一个结点的指针,最后一个结点的next指回表头结点。

为了节省大家的时间,在此先提示,不要挣扎于创建新的链表(判题程序有特殊处理的,此路不通)

提示

对于C/C++,将采用同一个判题程序:

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

typedef struct node {
    int data;
    // 其他数据域成员
    struct node* next;
} NODE;

NODE* merge2CircularLinkedList(NODE* head1, NODE* head2);

int main (int argc, char * argv[]) {

    /* 获取输入数据,细节隐藏不表 */
    /* 构建原始链表,细节隐藏不表 */

    NODE* head = merge2CircularLinkedList(head1, head2);

    /* 后续判题,细节隐藏不表 */
}

/* 你的代码将会被嵌入在这个部分 */

为了节省大家的时间,在此先提示,不要挣扎于创建新的链表(判题程序有特殊处理的,此路不通)
我来翻译一下这句话:
你想要malloc两个链表的大小,然后每次用类似归并排序的方法,这是会爆内存的;
你想要逐个malloc、free,你不知道隐藏字段是什么;
你想要memcpy整个结构体,对不起我有特殊的判题机制限制这样的做法;
你想要在原地址上神仙操作,大概会超时……
所以,老实讲,你要通过next指针指来指去