[数据结构与算法]数据结构之链表的合并(C语言)

1.定义结构体

typedef struct LNode {
	int data;
	struct LNode * next;
}LNode,*LinkList;

2.初始化方法

LinkList initList(LinkList l){
	l=(LNode *)malloc(sizeof(LNode));//分配内存
	l->next = NULL;
	return l;
}

3.将新节点插入到结尾

void createfromtail(LinkList l){
	LNode * p;
	LNode * node;
	node = l;
	int i = 1;
	int j;
	while(i!=0){
		scanf("%d",&j);
		if(j!=-1){
			p = (LNode *)malloc(sizeof(LNode));
			p->data = j;
			p->next = NULL;
			node->next = p;
			node = p;
		}else{
			i=0;
		}
	}
}

4.遍历

void getElems(LinkList l){
	printf("链表的内容为:\n");
	LNode * node;
	node = l;
	while(node->data != NULL){
		printf("%d\n",node->data);
		node = node->next;
	}
}

5.取值

LNode * getElem(LinkList l, int i){
	int j = 0;
	while(l->next != NULL && j < i){
		l = l->next;
		++j;
	}
	if(!l->next || j>i){
		return NULL;
	}
	return l;
}

6.查找数据元素在链表中的位置

int locateElem(LinkList l, int i){
	LNode *p = l->next;
	int j = 1;
	while(p && p->data != i){
		p = p->next;
		j++;
	}
	if(!p){
		return -1;
	}
	return j;
}

7.求链表长度

int listLength(LinkList A){
	int length = 0;
	LNode * p = A;
	while(p->next != NULL){
		++length;
		p = p->next;
	}
	return length;
}

8.合并链表(核心)

LinkList mergeList(LinkList A, LinkList B){
	int lenA = listLength(A);
	int lenB = listLength(B);
	LNode *p = A;
	while(p->next != NULL){
		p = p->next;
	}
	for(int i = 1; i <= lenB; i++){
		LNode * valB = getElem(B, i);
		if(locateElem(A, valB->data) == -1){
			p->next = valB;
			p = valB;
		}
	}
	p->next = NULL;
	getElems(A);
	return A;
}

9.main方法测试

int main(){

	LinkList A;
	A = initList(A);
	createfromtail(A);

	LinkList B;
	B = initList(B);
	createfromtail(B);
	
	A = mergeList(A, B);
	return 0;
}