一、問題:合并兩個有序單連結清單,合并後的單連結清單依然有序。
二、分析:
1.有如下兩個有序連結清單str1和str2
2.合并後的新連結清單的頭結點定義為newpHead,采用摘結點法:
sListNode* MergeList(sListNode* FirpHead, sListNode* SecpHead)
{
if(FirpHead == NULL)
{
return SecpHead;
}
if(SecpHead == NULL)
{
return FirpHead;
}
sListNode* newpHead = NULL;
sListNode* firCur = FirpHead, *secCur = SecpHead;
sListNode* tail = NULL;
if(firCur->data < secCur->data)
{
newpHead = firCur;
firCur = firCur->next;
}
else
{
newpHead = secCur;
secCur = secCur->next;
}
tail = newpHead;
while(firCur != NULL && secCur != NULL)
{
if(firCur->data < secCur->data)
{
tail->next = firCur;
firCur = firCur->next;
}
else
{
tail->next = secCur;
secCur = secCur->next;
}
tail = tail->next;
}
if(firCur == NULL)
{
tail->next = secCur;
}
if(secCur == NULL)
{
tail->next = firCur;
}
return newpHead;