C语言笔记29 •单链表经典算法OJ题-1.合并两个升序链表•

1.合并两个升序链表（创建头节点 简化代码）

ListNode* lowlisthead=(ListNode*)malloc(sizeof(ListNode));

新颖之处就是创建头节点（哨兵位）能够减少代码，不用每次都判断链表是否为NULL，

注意的是：最后函数的返回值是头节点的下一个地址（lowlisthead->next）

//========1.合并两个升序链表（创建头节点 简化代码）==========
typedef int SLTDataType;

typedef struct SListnode
{
	SLTDataType val;
	struct SListnode* next;
}ListNode;

ListNode* createNode(SLTDataType val)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->val = val;
	newnode->next = NULL;
	return newnode;
}

ListNode* mergeTwoLists(ListNode* L1, ListNode* L2)
{
	ListNode* lowlisthead=(ListNode*)malloc(sizeof(ListNode));
	ListNode* pcur = lowlisthead;

	while (L1 && L2)
	{
		if (L1->val < L2->val)
		{
		
			pcur->next = L1;
			pcur = pcur->next;
			L1 = L1->next;
		}
		else
		{
			pcur->next = L2;
			pcur = pcur->next;
			L2 = L2->next;
		}
		//pcur = pcur->next; 不能将判断语句里面的节点指针的移动 放在这里 ，确保在每次链接节点后正确地移动当前指针 pcur
	}
	if (L1)
	{
		pcur->next = L1;
	}
	if (L2)
	{
		pcur->next = L2;
	}
	return lowlisthead->next;

}

int main()
{
	ListNode* list1, * list2;//创建两个链表

	list1 = createNode(1);
	list1->next = createNode(2);
	list1->next->next = createNode(4);

	list2 = createNode(1);
	list2->next = createNode(3);
	list2->next->next = createNode(5);

	ListNode* head = mergeTwoLists(list1, list2);
	while (head)
	{
		printf("%d ", head->val);
		head = head->next;
	}
	return 0;
}

2.合并两个升序链表（不创建头节点） 

//2.合并两个升序链表（不创建头节点）

typedef int SLTDataType; 

typedef struct SListnode
{
	SLTDataType val;
	struct SListnode* next;
}ListNode;

ListNode* createNode(SLTDataType val)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->val = val;
	newnode->next = NULL;
	return newnode;
}

//ListNode* mergeTwoLists(ListNode* L1, ListNode* L2)
//{
//	ListNode* lowlisthead, * highlisthead;
//	lowlisthead = highlisthead = NULL;
//	
//	ListNode* pcur1, *pcur2;
//	pcur1 =lowlisthead;
//	pcur2 = highlisthead;
//	while(L1 && L2)
//	{
//		if (L1->val < L2->val)
//		{
//			if (lowlisthead == NULL)
//			{
//				lowlisthead = L1;
//			}
//			else
//			{
//				pcur1->next = L1;
//				pcur1 = pcur1->next;
//			}
//			L1 = L1->next;
//		}
//		else
//		{
//			if (highlisthead == NULL)
//			{
//				highlisthead = L2;
//			}
//			else
//			{
//				pcur2->next = L2;
//				pcur2 = pcur2->next;
//			}
//			L2 = L2->next;
//		}
//	}
//	if (L1)
//	{
//		pcur1->next = L1;
//	}
//	if (L2)
//	{
//		pcur2->next = L2;
//	}
//
//}

ListNode* mergeTwoLists(ListNode* L1, ListNode* L2)
{
	ListNode* lowlisthead, * pcur;
	pcur = lowlisthead= NULL;
	
	while (L1 && L2)
	{
		if (L1->val < L2->val)
		{
			if (lowlisthead == NULL)
			{
				lowlisthead = pcur = L1;
			}
			else
			{
				pcur->next = L1;
				pcur = pcur->next;
			}
			L1 = L1->next;
		}
		else
		{
			if (lowlisthead == NULL)
			{
				lowlisthead = pcur = L2;
			}
			else
			{
				pcur->next = L2;
				pcur = pcur->next;
			}
			L2 = L2->next;
		}
		//pcur = pcur->next; 不能将判断语句里面的节点指针的移动 放在这里 ，确保在每次链接节点后正确地移动当前指针 pcur
	}
	if (L1)
	{
		pcur->next = L1;
	}
	if (L2)
	{
		pcur->next = L2;
	}
	return lowlisthead;

}

int main()
{
	ListNode* list1,*list2;//创建两个链表

	list1 = createNode(1);
	list1->next= createNode(2);
	list1->next->next = createNode(4);

	list2 = createNode(1);
	list2->next = createNode(3);
	list2->next->next = createNode(5);

	ListNode* head = mergeTwoLists(list1, list2);
	while(head)
	{
		printf("%d ", head->val);
		head = head->next;
	}
	return 0;
}