c++中合并兩個有序鏈表的方法？這個問題可能是我們日常學習或工作經常見到的。希望通過這個問題能讓你收獲頗深。下面是小編給大家帶來的參考內容，讓我們一起來看看吧！
1.題目要求
這是一道求職面試時經常要求手寫或者機試的經典題目。
已知兩個鏈表head1和head2各自有序，請把它們合并成一個鏈表依然有序。結果鏈表要包含head1和head2的所有節點，即使節點值相同。
注意：不能開辟新空間來存儲合并后的鏈表。如果第一次做該題，很容易會想到使用新鏈表來存儲合并后的有序鏈表。雖然可以如此實現，但是不符合常規解法和面試官的要求。
2.非遞歸實現
算法過程：
輸入：兩個有序的單鏈表head1與head2；
輸出：合并后的有序單鏈表mergeHead；
算法描述：
（1）如果head1或head2為空鏈表，則直接返回另外一個鏈表；
（2）選擇head1與head2鏈表當前節點值較小的節點，掛接到后并后的鏈表mergeHead；
（3）重復步驟2，直到鏈表head1或者head2遍歷完成，未遍歷完的鏈表，直接掛接到mergeHead的尾節點。
具體實現如下：
#include <sstream>
#include <iostream>
using namespace std;
struct ListNode
{
int value;
ListNode* next;
ListNode() {value=0;next=NULL;}
ListNode(int value,ListNode* next = NULL):value(value),next(next){}
};
//@brief:非遞歸實現兩個有序單鏈表
//@注意：兩個鏈表需要從小到大順序排列
ListNode* mergeOrderedLinkedList(ListNode* head1,ListNode* head2)
{
if (head1 == NULL)
{
return head2;
}
else if(head2 == NULL)
{
return head1;
}
ListNode* mergeHead = NULL;
if (head1->value<head2->value)
{
mergeHead=head1;
head1=head1->next;
}
else
{
mergeHead = head2;
head2 = head2->next;
}
ListNode* tmpNode = mergeHead;
while(head1&&head2)
{
if(head1->value<head2->value)
{
mergeHead->next = head1;
head1 = head1->next;
}
else
{
mergeHead->next = head2;
head2 = head2->next;
}
mergeHead = mergeHead->next;
}
if (head1)
{
mergeHead->next = head1;
}
if (head2)
{
mergeHead->next = head2;
}
return tmpNode;
}
//打印鏈表
void printLinkedList(ListNode* head)
{
while(head)
{
cout<<head->value<<" ";
head=head->next;
}
cout<<endl;
}
int main(int argc,char* argv[])
{
ListNode* head1=NULL,*curList1=NULL,*head2=NULL,*curList2=NULL;
string strIn;
int value;
cout<<"創建鏈表1，從小到大順序輸入鏈表1："<<endl;
getline(cin,strIn);
stringstream ss(strIn);
cout<<"ss0 strIn:"<<ss.str()<<endl;
while(ss>>value) //從string中按照空格讀取int
{
ListNode* newNode1=new ListNode;
newNode1->value=value;
if(head1==NULL && curList1==NULL)
{
head1=newNode1;
curList1=newNode1;
}
else
{
curList1->next=newNode1;
curList1=curList1->next;
}
}
cout<<"創建鏈表2，從小到大順序輸入鏈表2："<<endl;
getline(cin,strIn);
ss.clear(); //清空狀態
ss.str(""); //清空內容
ss<<strIn; //重新輸出至string
cout<<"ss1 strIn:"<<ss.str()<<endl;
while(ss>>value) //從string中按照空格讀取int
{
ListNode* newNode2=new ListNode;
newNode2->value=value;
if(head2==NULL && curList2==NULL)
{
head2=newNode2;
curList2=newNode2;
}
else
{
curList2->next=newNode2;
curList2=curList2->next;
}
}
//合并兩個有序鏈表
ListNode* mergeHead=mergeOrderedLinkedList(head1,head2);
//打印鏈表
cout<<"合并后鏈表："<<endl;
printLinkedList(mergeHead);
}運行程序，輸出結果：
從小到大順序輸入鏈表1：
1 2 3 5
ss0 strIn:1 2 3 5
從小到大順序輸入鏈表2：
3 4 5 6 7 8
ss1 strIn:3 4 5 6 7 8
合并后鏈表：
1 2 3 3 4 5 5 6 7 8
3.遞歸實現
從上面合并兩個有序鏈表的步驟中可以看出，每次合并的步驟（2）都是一樣的，由此我們想到了遞歸。具體實現如下：
//@brief:遞歸實現兩個有序單鏈表
//@注意：兩個鏈表需要從小到大順序排列
ListNode* mergeOrderedLinkedListRecursion(ListNode* head1,ListNode* head2)
{
if(head1 == NULL)
{
return head2;
}
else if(head2 == NULL)
{
return head1;
}
ListNode* mergeHead = NULL;
if(head1->value<head2->value)
{
mergeHead=head1;
mergeHead->next=mergeOrderedLinkedListRecursion(head1->next,head2);
}
else
{
mergeHead=head2;
mergeHead->next=mergeOrderedLinkedListRecursion(head1,head2->next);
}
return mergeHead;
}感謝各位的閱讀！看完上述內容，你們對c++中合并兩個有序鏈表的方法大概了解了嗎？希望文章內容對大家有所幫助。如果想了解更多相關文章內容，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
