7-51 两个有序链表序列的合并

7-51 两个有序链表序列的合并
https://pintia.cn/problem-sets/15/problems/2992

这道题算是数据结构的最基础的题目，很多数据结构入门的课程里面都有它的身影。

好久没练习，导致挺简单的一题也是wrong了几次才过。
这道题遇到的几个坑：

1. 合并链表时，对剩下的不为空链表要分情况讨论。
   剩下的不为空链表有两种可能，第一是合并剩下的，第二是压根没参与合并，因为 while (list1!=NULL && list2!= NULL)　语句直接跳过了合并的循环。这两种情况下头指针是不同的（一个为空，一个不为空）。
   如果没有考虑到这种情况，结果就是当只有一个链表为空时，程序会非法访问引发异常。
2. 打印链表时，需要考虑到链表头指针是否为空。
3. 仔细读题……（“若新链表为空，输出’NULL’”）

#include <stdio.h>
#include <string.h>
#include<stdlib.h>
typedef struct Node node;
typedef struct Node* ptr;

struct Node
{
	int data;
	ptr next;
};



ptr createList() {
	int a;
	ptr list= NULL,now = NULL;

	while (scanf("%d", &a), a != -1)
	{
		//新建节点
		ptr temp = (ptr)malloc(sizeof(node));
		temp->data = a;
		temp->next = NULL;

		if (list == NULL) {  //头节点
			list = temp;
			now = temp;
		}
		else  //now非头节点
		{
			now->next = temp;
			now = now->next;
		}
	}
	return list;
}


ptr mergeList(ptr list1, ptr list2) {
	ptr list = NULL, now = NULL;
	//非降序排列
	while (list1!=NULL && list2!= NULL)
	{
		if (list1->data > list2->data)
		{
			if (list == NULL)
			{
				list = list2;
				now = list2;
			}
			else {
				now->next = list2;
				now = now->next;
			}
				
			list2 = list2->next;
			now->next = NULL;
		}
		else 
		{
			if (list == NULL)
			{
				list = list1;
				now = list1;
			}
			else {
				now->next = list1;
				now = now->next;
			}

			list1 = list1->next;
			now->next = NULL;
		}
	}

	//执行到这里说明其一一定为空
	if (list1!= NULL )
	{
		if (now == NULL ) {

			now = list1;
			list = list1;
		}
		else
		{
			now->next = list1;
		}
			
	}
	else if (list2 != NULL)
	{
		if (now == NULL) {

			now = list2;
			list = list2;
		}
		else
		{
			now->next = list2;
		}
	}

	return list;
}

void print(ptr list) {
	if (list!= NULL)
	{
		printf("%d", list->data);
		while (list->next != NULL)
		{
			list = list->next;
			printf(" %d", list->data);
		}
		printf("\n");
	}
	else
		printf("NULL");

}
int main()
{
	int a;
	ptr list1 = createList();
	ptr list2 = createList();

	ptr list = mergeList(list1 ,list2);
	print(list);

	return 0;
}