本文實例為大家分享了C++合并兩個排序的鏈表，供大家參考，具體內(nèi)容如下
創(chuàng)新互聯(lián)主要從事網(wǎng)站設(shè)計制作、成都做網(wǎng)站、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)余姚,十年網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18982081108
問題描述
輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。
重慶分公司
重慶分公司
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
方法一
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
ListNode* newList = NULL; //新鏈表頭
ListNode* newListRear = NULL; //新鏈表尾
// 先處理某個鏈表為空的情形
if (pHead1 == NULL){
return pHead2;
}
if (pHead2 == NULL){
return pHead1;
}
// 把數(shù)值小的結(jié)點放入新鏈表，生成頭節(jié)點
if (pHead1->val <= pHead2->val){
newList = pHead1;
newListRear = pHead1;
pHead1 = pHead1->next;
}else{
newList = pHead2 ;
newListRear = pHead2;
pHead2 = pHead2->next;
}
// 兩表均不空的情形下，遍歷
while (pHead1 != NULL && pHead2 != NULL) {
if (pHead1->val <= pHead2->val) {
newListRear->next =pHead1;
newListRear = pHead1;
pHead1 = pHead1->next;
}else{
newListRear->next =pHead2;
newListRear = pHead2;
pHead2 = pHead2->next;
}
}
//某一表為空時，把另一表接入新表表尾
if (pHead1 == NULL) {
newListRear->next = pHead2;
}
if (pHead2 == NULL) {
newListRear->next = pHead1;
}
return newList;
}
};方法二（遞歸思想）
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if (pHead1 == NULL){
return pHead2;
}
if (pHead2 == NULL){
return pHead1;
}
if (pHead1->val <= pHead2->val){ // pHead1為合并后的頭節(jié)點
pHead1->next = Merge(pHead1->next, pHead2);
return pHead1;
}else{ // pHead2 為合并后的頭節(jié)點
pHead2->next = Merge(pHead1, pHead2->next);
return pHead2;
}
}
};
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持創(chuàng)新互聯(lián)。
