王道数据结构 第二章 线性表（3） 编程题下半部分

1. 假设有两个元素值按递增次序排列的线性表，均以单链表形式存储，编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
   （考虑到使用递减排列，故使用头插法）

void unionDesc(linkList L1, linkList L2) {
    linkList p1 = L1->pNext, p2 = L2->pNext;
    linkList temp = nullptr;
    L1->pNext = nullptr; //任选其中一个链表的头部作为头指针
    while (p1 && p2) {
        if (p1->data <= p2->data) {
            temp = p1->pNext;
            p1->pNext = L1->pNext;
            L1->pNext = p1;
            p1 = temp;  //上述为头插的基本操作，需要熟练掌握
        }
        else {
            temp = p2->pNext;
            p2->pNext = L1->pNext;
            L1->pNext = p2;
            p2 = temp;
        }
    }
    if (p1) {
        p2 = p1;
    }
    while (p2) {
        temp = p2->pNext;
        p2->pNext = L1->pNext;
        L1->pNext = p2;
        p2 = temp;
    }
    free(L2);
}

2. 设A和B是两个单链表（带头结点），其中元素递增有序，设计一个算法从A和B公共元素中产生单链表C，要求不破坏A,B的结点。
   注意要设置变量temp，始终指向新链表的尾部。貌似没啥难度吧。

linkList commonNodeList(linkList L1, linkList L2) {
    linkList p1 = L1->pNext, p2 = L2->pNext;
    linkList c = (linkList)malloc(sizeof(Node));
    linkList temp = c, t;
    while (p1 && p2) {
        if ( p1->data < p2->data ) {
            p1 = p1->pNext;
        }
        else if (p2->data < p1->data) {
            p2 = p2->pNext;
        }
        else {
            t = (linkList)malloc(sizeof(Node));
            t->data = p1->data;
            temp->pNext = t;
            temp = temp->pNext;
            p1 = p1->pNext;
            p2 = p2->pNext;
        }
    }
    temp->pNext = nullptr;
    return c;
}

3. 已知两个链表A和B分别表示两个集合，元素递增排列，编制函数，求A和B的交集，并存放于A链表中。（这一题和上一题的主要区别是，本题结果保留在原来的链表上，链表的其余部分需要进行释放。）

void intersection(linkList &L1, linkList &L2) {
    linkList p1 = L1->pNext, p2 = L2->pNext, temp = L1;
    while (p1 && p2) {
        if (p1->data == p2->data) {
            temp->pNext = p1;
            temp = temp->pNext;
            linkList tNode = p2;
            p1 = p1->pNext;
            p2 = p2->pNext;
            free(tNode);//将不用的L2上的结点释放
        }
        else if (p1->data < p2->data) {
            linkList tNode = p1;
            p1 = p1->pNext;
            free(tNode);
        }
        else {
            linkList tNode = p2;
            p2 = p2->pNext;
            free(tNode);
        }
    }
    while (p1) {
        linkList tNode = p1;
        p1 = p1->pNext;
        free(tNode);
    }
    while (p2) {
        linkList tNode = p2;
        p2 = p2->pNext;
        free(tNode);
    }
    temp->pNext = nullptr;
    free(L2);
}

4. 两个整数序列，A和B，已经存入两个单链表中，设计算法判断B是否是A的连续子序列。

bool isSubsquence(linkList l1, linkList l2) {
    linkList p1 = l1->pNext, p2 = l2->pNext;
    while (p1 && p2) {
        if (p1->data == p2->data) {
            p1 = p1->pNext;
            p2 = p2->pNext;
        }
        else {
            p1 = p1->pNext;
            p2 = l2->pNext;
        }
    }
    if (p2 == nullptr) return 1;
    else return 0;
}

后面琐碎待补。