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;
}