合并两个排序的链表

/******************************************************************
题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然
是按照递增排序的。
******************************************************************/


#include<stdio.h>

struct ListNode
{
	int m_nValue;
	ListNode* m_pNext;
};
ListNode* createListNode(int value)
{
	ListNode* pNode = new ListNode();
	pNode->m_nValue = value;
	pNode->m_pNext  = NULL;
	return pNode;
}
void connectListNode(ListNode* pListNode1, ListNode* pListNode2)
{
	if(pListNode2 == NULL || pListNode2 == NULL)
		return;

	pListNode1->m_pNext = pListNode2;
}
ListNode* mergeSortedLists(ListNode* pList1, ListNode* pList2)
{
	if(!pList1)
		return pList2;
	if(!pList2)
		return pList1;

	ListNode* pHead;
	if(pList1->m_nValue <= pList2->m_nValue)
	{
		pHead = pList1;
		pHead->m_pNext = mergeSortedLists(pList1->m_pNext,pList2);
	}
	if(pList1->m_nValue > pList2->m_nValue)
	{
		pHead = pList2;
		pHead->m_pNext = mergeSortedLists(pList1,pList2->m_pNext);
	}
	return pHead;
}

void printList(ListNode* pNode)
{
	if(pNode == NULL)
		printf("List is NULL");

	while(pNode)
	{
		printf("%d\t",pNode->m_nValue);
		pNode = pNode->m_pNext;
	}
	printf("\n");
}
//单元测试
//两个非空链表
void test1()
{
	ListNode* pList1_Node1 = createListNode(1);
	ListNode* pList1_Node2 = createListNode(3);
	ListNode* pList1_Node3 = createListNode(5);
	ListNode* pList1_Node4 = createListNode(7);

	connectListNode(pList1_Node1,pList1_Node2);
	connectListNode(pList1_Node2,pList1_Node3);
	connectListNode(pList1_Node3,pList1_Node4);
	printList(pList1_Node1);

	ListNode* pList2_Node1 = createListNode(2);
	ListNode* pList2_Node2 = createListNode(4);
	ListNode* pList2_Node3 = createListNode(6);
	ListNode* pList2_Node4 = createListNode(8);

	connectListNode(pList2_Node1,pList2_Node2);
	connectListNode(pList2_Node2,pList2_Node3);
	connectListNode(pList2_Node3,pList2_Node4);
	printList(pList2_Node1);

	ListNode* pHead = mergeSortedLists(pList1_Node1,pList2_Node1);
	printList(pHead);
}
//一个空链表另一个非空
void test2()
{
	ListNode* pList1_Node1 = createListNode(1);
	ListNode* pList1_Node2 = createListNode(3);
	ListNode* pList1_Node3 = createListNode(5);
	ListNode* pList1_Node4 = createListNode(7);

	connectListNode(pList1_Node1,pList1_Node2);
	connectListNode(pList1_Node2,pList1_Node3);
	connectListNode(pList1_Node3,pList1_Node4);
	printList(pList1_Node1);


	ListNode* pHead = mergeSortedLists(pList1_Node1,NULL);
	printList(pHead);
}
//两个非空链表
void test3()
{
	ListNode* pHead = mergeSortedLists(NULL,NULL);
	printList(pHead);
}
int main()
{
	test1();
	test2();
	test3();
	return 0;
}

==参考剑指OFFER

合并两个排序的链表,布布扣,bubuko.com

合并两个排序的链表

原文：http://blog.csdn.net/walkerkalr/article/details/21032801