本文實例為大家分享了C++合并兩個排序的鏈表，供大家參考，具體內容如下
問題描述
輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。
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;
}
// 把數值小的結點放入新鏈表，生成頭節點
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為合并后的頭節點
pHead1->next = Merge(pHead1->next, pHead2);
return pHead1;
}else{ // pHead2 為合并后的頭節點
pHead2->next = Merge(pHead1, pHead2->next);
return pHead2;
}
}
};
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
