合并有序链表

一、题目

二、代码

1. 思想：将情况分为三种，大于和小于简单的合并，相等的时候需要额外考虑一些问题

哪些问题？

1.新表指针如何移动 2.两个子表指针如何移动

相等的时候，需要考虑新表指针的如何操作，

当新表中已经存在，两个子表指针目前所指节点的值，就只需将两个子表中重复的元素略过，

否则，则需要将这个值加入到新表，再将重复的元素略过。

2. 我的解答

#include<stdio.h>
#include<malloc.h>

typedef struct linkList {
	int value;
	struct linkList* next;
}list;

void insert_tail(list* L,int data) {
	if (L) {
		list* p = L;
		while (p->next) 
			p = p->next;
		list* newNode = (list*)malloc(sizeof(list));
		newNode->value = data;
		newNode->next = p->next;
		p->next = newNode;
	}
}

list* init(list* L,int n) {
	L = (list*)malloc(sizeof(list));
	L->next = NULL;
	int temp;
	for (int i = 0; i < n; i++) {
		scanf("%d", &temp);
		insert_tail(L, temp);
	}
	return L;
}

void print(list* L) {
	if (!L) return;
	list* p = L->next;
	while (p) {
		printf("%d ", p->value);
		p = p->next;
	}
	printf("\n");
}

list* merge(list* L1, list* L2) {
	if (!L1 || !L2) return L1 ? L1 : L2;
	list* p1 = L1->next, * p2 = L2->next, * p3 = L1;//L1子表指针p1 L2子表指针p2 L3新表指针p3
	while (p1 && p2) {
		if (p1->value == p2->value) {
			int temp = p1->value;
			if (p3 == L1 || p3->value != temp) {
				p3->next = p1;
				p1 = p1->next;
			}
			while (p1 && p1->value == temp)
				p1 = p1->next;
			while (p2 && p2->value == temp) 
					p2 = p2->next;		
		}
		else if (p1->value < p2->value) {
			p3->next = p1;
			p1 = p1->next;
		}
		else {
			p3->next = p2;
			p2 = p2->next;
		}
		p3 = p3->next;
	}
	p3->next = p1 ? p1 : p2;
	free(L2);
	return L1;
}

int main() {
	list* L1 = NULL;
	L1 = init(L1, 5);
	list* L2 = NULL;
	L2 = init(L2, 5);
	//合并
	list* L3 = merge(L1, L2);
	print(L3);
	return 0;
}