C语言实现两个有序链表的去重合并

清疚 2022-12-15 03:27 118阅读 0赞

有两种方式，第一种是将两个链表合并为一个新的链表。第二种方式是将一个链表合并到另一个链表上。

#include<stdio.h>
    #include <stdlib.h>
    typedef struct node {
    	int val;
    	struct node *next;
    }Node,*Pnode;
    
    //creat list
    int create_list(Pnode *head, int *arr, int len)
    {
    	int i;
    	Pnode tmp, tail;
    	if (NULL == arr )
    	{
    		printf("invailed parameter\n");
    		return -1;
    	}
    		
    	for (i = 0; i < len; i++)
    	{
    		tmp = (Node *)malloc(sizeof(Node));
    		if(NULL == tmp)
    		{
    			printf("failed to malloc\n");
    			return -1;		
    		}
    		if (NULL == *head)
    		{
    			*head = tail = tmp;
    		
    		}
    		else
    		{	
    			tail->next = tmp;
    			tail = tmp;
    		}
    
    		tmp->val = arr[i];
    		tmp->next = NULL;	
    	
    	}
    	
    	return 0;
    
    	
    }
    
    #if 1
    //修改原链表内容
    Pnode merge_list(Pnode head_a, Pnode head_b)
    {
    	if(NULL == head_a || NULL == head_b)
    	{
    		printf("invailed parameter\n");
    		return NULL;		
    	}
    	
    	Pnode tmpa, tmpb, fornt, tmpb_next;
    	
    	tmpb = head_b;
    
    	//b 添加到 a
    	while(tmpb)
    	{
    		tmpa = head_a;
    		while(tmpa && (tmpb->val > tmpa->val) )
    		{
    			fornt = tmpa;//保留前一个
    			tmpa = tmpa->next;
    		}
    			
    		//去重
    		if(tmpa && tmpb->val == tmpa->val)
    		{
    			tmpb_next = tmpb->next;
    			free(tmpb);
    			tmpb = tmpb_next;
    			continue;
    			
    		}
    		
    		tmpb_next = tmpb->next;
    		tmpb->next = fornt->next;
    		fornt->next = tmpb;
    		
    		tmpb = tmpb_next;
    		
    	}
    	
    	return head_a;
    	
    	
    	
    }
    #else
    
    //create new list
    Pnode merge_list(Pnode head_a, Pnode head_b)
    {
    	if(NULL == head_a || NULL == head_b)
    	{
    		printf("invailed parameter\n");
    		return NULL;		
    	}
    	
    	Pnode tmpa, tmpb, tmp, fornt, new_head = NULL, tail, new_node;
    	
    	tmpa = head_a;
    	tmpb = head_b;
    
    	//复制链表a
    	while(tmpa)
    	{
    		tmp = malloc(sizeof(Node));
    		tmp->val = tmpa->val;
    		if (NULL == new_head)
    		{
    			new_head = tail = tmp;
    		}
    		else
    		{
    			tail->next = tmp;
    			tail = tmp;
    		}
    		
    		tmpa = tmpa->next;
    	}
    	
    	
    	
    	//printf
    	tmp = new_head;
    	while(tmp)
    	{
    		printf("new val:%d\n", tmp->val);
    		tmp = tmp->next;
    		
    	}
    	
    	while(tmpb)
    	{	
    		tmp = new_head;
    
    		while(tmp && tmpb->val > tmp->val)
    		{
    			fornt = tmp;
    			tmp = tmp->next;
    		}
    #if 1	//去重功能
    		if (tmp && tmpb->val == tmp->val)
    		{
    			tmpb = tmpb->next;
    			continue;
    		}
    #endif		
    		new_node = malloc(sizeof(Node));
    		if (NULL == new_node)
    		{
    			printf("malloc failed\n");
    			return NULL;
    		}
    		
    		new_node->val = tmpb->val;
    		new_node->next = fornt->next;
    		fornt->next = new_node;
    		
    		tmpb = tmpb->next;
    				
    	}
    
    	return new_head;
    	
    }
    
    	
    #endif
    
    
    int main()
    {
    	Pnode head_a = NULL, tmp, head_b = NULL;
    	int a[] = {1,3,5,7,9,10,11,12};
    	int b[] = {2,4,6,7,8,10};
    	
    #if 0	
    	int i;
    	for (i = 0; i < 5; i++)
    	{
    		tmp = (Node *)malloc(sizeof(Node));
    		if(NULL == tmp)
    		{
    			printf("failed to malloc\n");
    			return -1;		
    		}
    		if (NULL == head_a)
    		{
    			head_a = tail = tmp;
    		
    		}
    		else
    		{	
    			tail->next = tmp;
    			tail = tmp;
    		}
    
    		tmp->val = a[i];
    		tmp->next = NULL;	
    	
    	}
    #endif	
    	create_list(&head_a, a, sizeof(a)/sizeof(a[0]));
    	create_list(&head_b, b, sizeof(b)/sizeof(b[0]));
    
    	tmp = head_a;
    	//printf
    	while(tmp)
    	{
    		printf("val:%d\n", tmp->val);
    		tmp = tmp->next;
    		
    	}
    	
    	tmp = head_b;
    	//printf
    	while(tmp)
    	{
    		printf("val:%d\n", tmp->val);
    		tmp = tmp->next;
    		
    	}
    	printf("merge list....\n");
    	tmp = merge_list(head_a, head_b);
    	while(tmp)
    	{
    		printf("val:%d\n", tmp->val);
    		tmp = tmp->next;
    		
    	}
    	
    }