(本博客旨在个人总结回顾)
题目描述:
输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如输入图3.7的链表1和链表2.则合并之后的升序链表如链表3所示。链表结点定义如下:
struct ListNode
{
int m_nValue;
ListNode* m_pNext;
};
解法一:
/*
* @name MergeList
* @brief 合并两个升序链表为一个升序链表
* @param [in] ListNode * pHead1
* @param [in] ListNode * pHead2
* @return ListNode*
*/
ListNode* MergeList(ListNode* pHead1, ListNode* pHead2)
{
if (NULL == pHead1)
{
return pHead2;
}
if (NULL == pHead2)
{
return pHead1;
}
ListNode* pNode = NULL;
ListNode* pNext = NULL;
ListNode* pHead = NULL;
while (pHead1 != NULL || pHead2 != NULL)
{
if (pHead1 == NULL)
{
pNext = pHead2;
pHead2 = pHead2->m_pNext;
}
else if (pHead2 == NULL)
{
pNext = pHead1;
pHead1 = pHead1->m_pNext;
}
else
{
if (pHead1->m_nValue <= pHead2->m_nValue)
{
pNext = pHead1;
pHead1 = pHead1->m_pNext;
}
else
{
pNext = pHead2;
pHead2 = pHead2->m_pNext;
}
}
if (pNode == NULL)
{
pNode = pNext;
pHead = pNode;
}
else
{
pNode->m_pNext = pNext;
pNode = pNext;
}
}
return pHead;
}
解法二:递归实现
/*
* @name MergeListRecursion
* @brief 合并两个升序链表为一个升序链表(递归实现)
* @param [in] ListNode * pHead1
* @param [in] ListNode * pHead2
* @return ListNode*
*/
ListNode* MergeListRecursion(ListNode* pHead1, ListNode* pHead2)
{
if (NULL == pHead1)
{
return pHead2;
}
if (NULL == pHead2)
{
return pHead1;
}
ListNode* pHead = NULL;
if (pHead1->m_nValue <= pHead2->m_nValue)
{
pHead = pHead1;
pHead->m_pNext = MergeListRecursion(pHead1->m_pNext, pHead2);
}
else
{
pHead = pHead2;
pHead->m_pNext = MergeListRecursion(pHead1, pHead2->m_pNext);
}
return pHead;
}
测试代码:
/*
* @name PrintList
* @brief 打印链表
* @param [in] ListNode * pHead
* @return void
*/
void PrintList(ListNode* pHead)
{
if (NULL == pHead)
{
return;
}
while (pHead != NULL)
{
cout << pHead->m_nValue << " ";
pHead = pHead->m_pNext;
}
cout << endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
//测试1题描述例子
ListNode* pHead1 = new ListNode();
pHead1->m_nValue = 1;
ListNode* pTmp = new ListNode();
pTmp->m_nValue = 3;
pHead1->m_pNext = pTmp;
pTmp->m_pNext = new ListNode();
pTmp = pTmp->m_pNext;
pTmp->m_nValue = 5;
pTmp->m_pNext = new ListNode();
pTmp = pTmp->m_pNext;
pTmp->m_nValue = 7;
ListNode* pHead2 = new ListNode();
pHead2->m_nValue = 2;
pTmp = new ListNode();
pTmp->m_nValue = 4;
pHead2->m_pNext = pTmp;
pTmp->m_pNext = new ListNode();
pTmp = pTmp->m_pNext;
pTmp->m_nValue = 6;
pTmp->m_pNext = new ListNode();
pTmp = pTmp->m_pNext;
pTmp->m_nValue = 8;
PrintList(pHead1);
PrintList(pHead2);
cout << "测试题目第1个链表为空:" << endl;
PrintList(MergeList(NULL, pHead2));
cout << "测试题目第2个链表为空:" << endl;
PrintList(MergeList(pHead1, NULL));
cout << "测试题目2个链表为空:" << endl;
PrintList(MergeList(NULL, NULL));
cout << "测试题目2个链表都只有1个结点:" << endl;
ListNode* pNode1 = new ListNode();
pNode1->m_nValue = 9;
ListNode* pNode2 = new ListNode();
pNode2->m_nValue = 10;
PrintList(MergeList(pNode1, pNode2));
cout << "测试题目例子:" << endl;
PrintList(MergeList(pHead1, pHead2));
system("pause");
return 0;
}
运行结果: