2つのソートされたチェーンテーブルをマージ(C++実装)
2153 ワード
問題の説明
2つの単調に増加したチェーンテーブルを入力し、2つのチェーンテーブルの合成後のチェーンテーブルを出力します.もちろん、合成後のチェーンテーブルは単調で減少しない規則を満たす必要があります.
方法1
方法二(再帰思想)
2つの単調に増加したチェーンテーブルを入力し、2つのチェーンテーブルの合成後のチェーンテーブルを出力します.もちろん、合成後のチェーンテーブルは単調で減少しない規則を満たす必要があります.
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
方法1
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;
}
}
};