两递增归并为递减到原位

假设有两个按元素递增次序排列的线性表，均以单链表形式存储。将这两个单链表归并为一个按元素递减次序排列的单链表，并要求利用原来两个单链表的节点存放归并后的单链表

算法思想

因为两链表已按元素值递增次序排列，将其合并时，均从第一个节点起进行比较，将小的链入链表中，同时后移链表工作指针
要求结果链表按元素值递减次序排列，在归并的同时，将链表节点逆置

将la断开，置为NULL

cura和curb开始遍历，取小的头插，相当于逆置
cura<curb，
用next保存cura的下一个节点

将cura的next指向la的next，即NULL

la的next指向cura

cura指向next

完成头插

LinkList Union(LinkList la, lb)
{// cura和curb分别是链表A和B的工作指针，next保存下一个节点LNode* cura = la->next, *curb = lb->next, *next;la->next = NULL;      // la作结果链表的头指针，先将结果链表置为NULLwhile (cura && curb){if (cura->data <= curb->data){// 将cura的后继节点存于nextnext = cura->next;// 将cura节点链于结果表中，同时逆置cura->next = la->next;la->next = cura;// 恢复cura为当前待比较节点cura = next;}else{next = curb->next;curb->next = la->next;la->next = curb;curb = next;}}// 将la表剩余的部分链入结果表，并逆置// 两个while只能运行一个while (cura){next = cura->next;cura->next = la->next;la->next = cura;cura = next;}while (curb){next = curb->next;curb->next = la->next;la->next = curb;curb = next;}return la;
}

b表归并到a表

设有两个无头节点的单链表，头指针分别为ha，hb，两链表的数据都按递增次序存放，现要求将hb表归并到ha表中，且归并后ha仍为递增，归并中ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏

算法思想

由于无头节点，为方便建立头节点，最后删掉
数据相同的节点，不合并到结果链表中
hb表不能被破坏，即要归并的时候，要创建新节点

申请头节点la指向ha的头节点，cura和curb分别指向ha和hb的第一个节点，prev指针指向cura的前一个节点

cura和curb向后遍历，如果cura小于curb
prev的next指向cura，prev指向cura，cura指向它的下一个

如果cura大于curb
malloc一个new节点，使得new的data等于curb的data

prev的next指向new，prev指向new，curb指向它的下一个节点

如果cura等于curb
cura链入结果链表，curb继续往后遍历

LinkList Union(LinkList ha, hb)
{// 申请头节点，以便操作LinkList la;la = (LinkList)malloc(sizeof(LNode));la->next = ha;// cura时ha链表的工作指针LNode* cura = ha;// curb时hb的工作指针LNode* curb = hb;// prev指向当前待合并节点的前驱LNode* prev = la;while(cura && curb){// 处理ha中的数据if (cura->data < curb->data){prev->next = cura;prev = cura;cura = cura->next;}// 处理hb中的数据else if (cura->data > curb->data){// 申请空间LNode* new = (LNode*)malloc(sizeof(LNode));// 将新节点链入结果链表			new->data = curb->data;prev->next = new;prev = new;// 链表中工作节点后移curb = curb->next;}// 处理cura->data == curb->dataelse{// 只要ha的数据prev->next = cura;prev = cura;cura = cura->next;// 不要hb的数据curb = curb->next;}}// 将两链表中剩余部分链入结果链表if (cura)prev->next = cura;if (curb)prev->next = curb;// 释放头节点free(la);return ha;
}

两递减归并到新链表

已知头指针分别为la和lb的带头节点的单链表中，节点按元素值非递减有序排列。
将la和lb两链表归并成一个节点按元素值非递减有序排列的单链表，头指针为lc

LinkList Union(LinkList &la, &lb)
{LNode* cura = la->next, curb = lb->next;LinkList lc = (LinkList)malloc(sizeof(LNode));LNode* curc = lc;while (cura && curb){if (cura->data < curb->data){curc->next = cura;curc = cura;cura = cura->next;}else{curc->next = curb;curc = curb;curb = curb->next;}}if (cura)curc->next = cura;if (curb)curc->next = curb;free(la);free(lb);return lc;
}