基于单链表：

/************************************************************
* Windows 10下，Dev-C++ 6.6、Visual Studio 2019 中测试通过	*
*															*
* @file		习题2.6.c										*
*															*
* @brief	习题2.6											*
*			设有两个按数据元素递增有序的顺序表 A 和 B		*
*			（单链表 A 和 B），编一程序将 A 表 和 B 表		*
*			归并成一个新的递增有序的顺序表 C（单链表 C，	*
*			值相同的的数据元素均保留在 C 表中）。			*
*															*
* @author	CSDN@洛必不达法则								*
*															*
* @date		2021-10-17										*
*************************************************************/

#define _CRT_SECURE_NO_WARNINGS		// VS2019中 scanf 被认为是不安全的，需要加上该宏才能使用
#include <stdio.h>
#include <stdlib.h>

/**
* @brief	定义链表节点结构体
*/
typedef struct node
{
	int data;			// 节点数据
	struct node* next;	// 后继指针
}LNode, * LPList;

/**
* @brief	创建链表节点
* @param nData	节点数据
* @return	创建成功的节点的地址
*/
LNode* CreateNode(int nData)
{
	LNode* pNode = (LNode*)malloc(sizeof(LNode));
	if (!pNode)
	{
		printf("内存申请失败！\n");
		return NULL;
	}
	pNode->next = NULL;
	pNode->data = nData;
	return pNode;
}

/**
* @brief	创建链表
* @return	创建的链表的头节点的地址
*/
LPList CreateList()
{
	LNode* pHead = CreateNode(-12345);
	LNode* pTail = pHead;
	int nodeData = 0;
	// 输入非数字时结束循环
	while (scanf("%d", &nodeData))
	{
		LNode* pNode = CreateNode(nodeData);
		pTail->next = pNode;
		pTail = pNode;
	}
	return pHead;
}

/**
* @brief	遍历打印链表数据
* @param lpList	需要遍历的链表
*/
void PrintList(LPList lpList)
{
	LNode* pMove = lpList->next;
	while (pMove != NULL)
	{
		printf("%d  ", pMove->data);
		pMove = pMove->next;
	}
	printf("\n");
}

/**
* @brief	获得一个链表的拷贝本（地址不一样）
* @param lpList  需要拷贝的链表
* @return	链表的拷贝
*/
LPList CopyList(LPList lpList)
{
	LNode* pMove = lpList->next;
	LNode* pCopy = CreateNode(-12345);
	LNode* pTail = pCopy;
	while (pMove != NULL)
	{
		LNode* pNode = CreateNode(pMove->data);
		pTail->next = pNode;
		pTail = pNode;
		pMove = pMove->next;
	}
	return pCopy;
}

/**
* @brief	合并两个递增链表，合并后仍为递增，且不破坏合并的两个链表
* @param lpListA  待合并的链表A
* @param lpListB  待合并的链表B
* @return	合并后的递增链表
*/
LPList MergeList(LPList lpListA, LPList lpListB)
{
	/// 合并后的链表，作为结果返回
	LPList lpListC = CopyList(lpListA);

	/// lpListB链表的移动指针
	LNode* pMoveB = lpListB->next;

	/// lpListC链表的移动指针
	LNode* pMoveC = lpListC;
	
	while (pMoveC->next != NULL)
	{
		while (pMoveB != NULL)
		{
			if (pMoveC->next->data >= pMoveB->data)
			{
				LNode* pInsert = CreateNode(pMoveB->data);
				pInsert->next = pMoveC->next;
				pMoveC->next = pInsert;
				pMoveC = pInsert;
				pMoveB = pMoveB->next;
			}
			else
			{
				break;
			}
		}
		if (pMoveC->next->next == NULL)
		{
			pMoveC->next->next = pMoveB;
			break;
		}
		pMoveC = pMoveC->next;
	}
	return lpListC;
}

int main()
{
	printf("\t********* 习题2.6 *********\n");
	printf("递增输入链表 A 节点数据（输入任意字母字符结束）：\n");
	LPList A = CreateList();
	setbuf(stdin, NULL);
	printf("\n递增输入链表 B 节点数据（输入任意字母字符结束）：\n");
	LPList B = CreateList();

	printf("\n链表 A：\n");
	PrintList(A);
	printf("链表 B：\n");
	PrintList(B);

	LPList C = MergeList(A, B);
	printf("\n合并后链表 C：\n");
	PrintList(C);

	return 0;
}