题目很简单：
输入两个链表(不一定有序)，合并这两个链表并使新链表中的结点是按照递增排序。
其他不多说，看一下代码：
/*
author：http://blog.csdn.net/richerg85
*/
#include "stdafx.h"
#include <iostream>
using namespace std;
struct ListNode
{
int m_nValue;
ListNode *m_pNext;
};
ListNode *MergeTwoList(ListNode *pFirstNodeHead, ListNode *pSecondNodeHead)
{
if ( pFirstNodeHead == NULL )
return pSecondNodeHead;
if ( pSecondNodeHead == NULL )
return pFirstNodeHead;
//normal merge
ListNode *pFirstNode = pFirstNodeHead;
ListNode *pSecondNode = pSecondNodeHead;
ListNode *pMergeHead = NULL;
ListNode *pCurNode = NULL;
if ( pFirstNode->m_nValue < pSecondNode->m_nValue)
{
pMergeHead = pFirstNodeHead;
pFirstNode = pFirstNode->m_pNext;
pCurNode = pMergeHead;
}
else
{
pMergeHead = pSecondNodeHead;
pSecondNode = pSecondNode->m_pNext;
pCurNode = pMergeHead;
}
while ( pFirstNode!=NULL && pSecondNode != NULL )
{
if ( pFirstNode->m_nValue < pSecondNode->m_nValue)
{
pCurNode->m_pNext = pFirstNode;
pCurNode = pFirstNode;
pFirstNode = pFirstNode->m_pNext;
}
else
{
pCurNode->m_pNext = pSecondNode;
pCurNode = pSecondNode;
pSecondNode = pSecondNode->m_pNext;
}
if ( pFirstNode == NULL )
pCurNode->m_pNext = pSecondNode;
if ( pSecondNode == NULL )
pCurNode->m_pNext = pFirstNode;
}
return pMergeHead;
}
int GetNodeLen(ListNode *pHead)
{
if ( !pHead )
return 0;
ListNode *pCur =pHead;
int nCnt = 0;
while ( pCur )
{
nCnt++;
pCur = pCur->m_pNext;
}
return nCnt;
}
//bubble sort
void SortNode(ListNode *&pHead)
{
ListNode *p1 = NULL;
ListNode *p2 = NULL;
if ( !pHead )
return;
int nCnt = GetNodeLen(pHead);
for (int i=0; i<nCnt-1; i++)
{
p1 = pHead;
for (int j=0; j<nCnt-i-1; j++)
{
p2 = p1->m_pNext;
if ( p1->m_nValue > p2->m_nValue )
{
int k = p1->m_nValue;
p1->m_nValue = p2->m_nValue;
p2->m_nValue = k;
}
p1 = p1->m_pNext;
}
}
}
//insert node
void InsertNode(ListNode *&pHead)
{
ListNode *pListNode = NULL;
ListNode *pCurNode = NULL;
if ( pHead == NULL )
{
pHead = new ListNode();
cin >>pHead->m_nValue;
if ( pHead->m_nValue == -1 )//-1,end
{
pHead = NULL;
return;
}
pHead->m_pNext = NULL;
pCurNode = pHead;
}
while(1)
{
pListNode = new ListNode();
cin >> pListNode->m_nValue;
if ( pListNode->m_nValue == -1 )
break;
pListNode->m_pNext = NULL;
pCurNode->m_pNext = pListNode;
pCurNode = pListNode;
}
}
//print list
void PrintList(ListNode *pHead)
{
if ( pHead )
{
ListNode *pCur = pHead;
while ( pCur )
{
cout << pCur->m_nValue << " ";
pCur = pCur->m_pNext;
}
cout << endl;
}
}
int main()
{
ListNode *pFistNode = NULL;
ListNode *pSecondNode = NULL;
cout<<"Please input first link:(-1 end)"<<endl;
InsertNode(pFistNode);
PrintList(pFistNode);
cout<<"Please input second link:(-1 end)"<<endl;
InsertNode(pSecondNode);
PrintList(pSecondNode);
cout<<"sort first:"<<endl;
SortNode(pFistNode);
PrintList(pFistNode);
cout<<"sort second:"<<endl;
SortNode(pSecondNode);
PrintList(pSecondNode);
ListNode *pMergeNode = MergeTwoList(pFistNode, pSecondNode);
cout<<"After merge:"<<endl;
PrintList(pMergeNode);
return 0;
}
运行：
补充：
单链表逆转
void ReverseList(ListNode *&pHead)
{
if ( !pHead )
return;
ListNode *pPre,*pCur,*pNext;
pPre = pHead;
pCur = pPre->m_pNext;
while ( pCur )
{
pNext = pCur->m_pNext;
pCur->m_pNext = pPre;
pPre = pCur;
pCur = pNext;
}
pHead->m_pNext = NULL;
pHead = pPre;
}
说明：*&，为指针的引用
删除一个单向链表的最中间元素，不能使用两次循环(申请两个指针，步长不一样)。
void delMiddle(link *head)
{
if(head == NULL)
return;
else if(head->next == NULL)
{
delete head;
return;
}
else
{
link *low = head;
link *fast = head->next;
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
if(fast == NULL)
break;
low = low->next;
}
link *temp = low->next;
low->next = low->next->next;
delete temp;
}
}