算法设计：将降序链表插入升序链表

问题描述: 假定单链表的结点结构为 (KEY, LINK)，设两个单链表的头指针分别为 F 和 R，F 所指单链表中各结点已按关键词升序排列，R 所指单链表中各结点已按关键词降序排列，请设计一个算法，将 R 所指单链表中的结点都插入到 F 所指的单链表中，使得插入后得到的单链表 (F 指向的) 仍按关键词升序排列。

算法思路:

从 R 所指单链表中取出一个结点，然后按照升序的方式插入到 F 所指单链表中。

关键步骤:

定义指针 p 指向 F 所指单链表的头结点，q 指向 R 所指单链表的头结点的下一个结点。
遍历 R 所指单链表，每次取出一个结点 r。
将 p 指针从头结点开始遍历 F 所指单链表，找到第一个大于等于 r 结点关键字的结点 pre。
将 r 结点插入到 pre 结点后面，更新 p 指针指向插入的结点。
将 q 指针从当前位置开始遍历 R 所指单链表，找到第一个小于等于 p 指针所指结点的结点 s。
将 q 指针所指结点插入到 p 指针所指结点的前面，更新 p 指针指向插入的结点，继续遍历 R 所指单链表。
重复步骤 2-6，直到遍历完 R 所指单链表。

时间和空间复杂度:

时间复杂度为 O(n^2)。
空间复杂度为 O(1)。

代码实现:

void MergeList(LinkList &F, LinkList &R) {
    ListNode *p = F->next, *q = R->next->next;
    while (q != NULL) {
        ListNode *r = q;
        q = q->next;
        ListNode *pre = p, *cur = p->next;
        while (cur != NULL && cur->key < r->key) {
            pre = cur;
            cur = cur->next;
        }
        r->next = pre->next;
        pre->next = r;
        p = r;
        while (q != NULL && q->key >= p->key) {
            r = q;
            q = q->next;
            pre = p, cur = p->next;
            while (cur != NULL && cur->key < r->key) {
                pre = cur;
                cur = cur->next;
            }
            r->next = pre->next;
            pre->next = r;
            p = r;
        }
    }
}

说明:

该代码假设已经定义了单链表的结构体 ListNode 和 LinkList。
代码中 key 是指结点的关键字。
代码中的 -> 表示指向成员变量或函数。
代码中的 NULL 指示空指针。