C语言：非减链表的合并

╰半橙微兮° 2022-08-03 05:18 37阅读 0赞

/*
    	a,b是两个非减单链表，把它们合并成一个新的链表，元素也是非减的
    */
    # include <stdio.h>
    # include <malloc.h>
    
    typedef struct node
    {
    	int data;
    	struct node * pNext;
    
    }NODE, *PNODE;
    
    
    PNODE creat_list();  //创建链表
    void travese(PNODE pHead);  //遍历链表
    PNODE union_list(PNODE pA, PNODE pB);  //有顺序的合并两个链表
    
    int main(void)
    {
    	//创建链表A
    	PNODE pA = creat_list();
    	travese(pA);
    
    	//创建链表B
    	PNODE pB = creat_list();
    	travese(pB);
    
    	//生成合并链表C
    	PNODE pC = union_list(pA, pB);
    	travese(pC);
    
    	return 0;
    }
    
    //创建链表
    PNODE creat_list()
    {
    	int i, val;
    	int len;
    
    	PNODE pHead = (PNODE)malloc(sizeof(NODE));  //创建头结点
    	pHead->pNext = NULL;
    
    	PNODE pNew;
    	PNODE pTail = pHead;  //指向尾节点
    
    
    	printf("链表的长度为 len = ");
    	scanf("%d", &len);
    
    	for(i = 0; i < len; i++)
    	{
    		printf("链表的第%d个元素：", i+1);
    		scanf("%d", &val);
    
    		pNew = (PNODE)malloc(sizeof(NODE));
    
    		pNew->data = val;
    		pNew->pNext = NULL;
    
    		pTail->pNext = pNew;
    		pTail = pNew;
    	}
    	return pHead;
    }
    
    //遍历链表
    void travese(PNODE pHead)
    {
    	PNODE p = pHead->pNext;  //p指向头结点
    
    	while(p)
    	{
    		printf("%d ", p->data);
    		p = p->pNext;
    	}
    	printf("\n");
    }
    
    //合并两个非减 单链表，至一个新的非减 单链表
    PNODE union_list(PNODE pA, PNODE pB)
    {
    	PNODE pC = (PNODE)malloc(sizeof(NODE)); //合并后链表的头结点
    	pC->pNext = NULL;
    	PNODE pTail = pC;  //指向链表C的尾节点
    
    	PNODE pa = pA->pNext;
    	PNODE pb = pB->pNext;
    
    	while(pa && pb)
    	{
    		if(pa->data <= pb->data)  //当前A中节点的值 大于 B中节点的值
    		{
    			pTail->pNext = pa;  //指向A中当前节点
    			pTail = pa;
    			pa = pa->pNext;
    		}
    		else
    		{
    			pTail->pNext = pb;
    			pTail = pb;
    			pb = pb->pNext;
    		}
    	}
    
    	if(pa)  //若链表A中有剩余节点
    	{
    		pTail->pNext = pa;
    	}
    	if(pb)  //若链表B中有剩余节点
    	{
    		pTail->pNext = pb;
    	}
    
    	return pC;
    }

![Center][]

[Center]: /images/20220731/570e28d3c2484197a4a56e0927cf6a3c.png