Q25合并連結清單

Q25合并連結清單 （順序合并+遞歸）

文章目錄

• Q25合并連結清單 （順序合并+遞歸）
• • 題目：
  • 思路
  • • 1.順序合并
    • 2.遞歸

題目：

輸入兩個單調遞增的連結清單，輸出兩個連結清單合成後的連結清單，當然我們需要合成後的連結清單滿足單調不減規則。

思路

直覺上并沒有特别複雜的地方。但是寫起來需要注意

nullptr

的影響

1.順序合并

1. 找出兩個連結清單中，首元素較小的連結清單頭重新定義為p1，另一個為p2。
2. 當p2的val滿足處于[p1, p1+1)内val時，将p2合并至p1後，不然就讓P1往前移
   • 注意判斷p1+1是否為空！！
3. 合并時，注意p1, p2的順序！

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==nullptr)
            return pHead2;
        if(pHead2==nullptr)
            return pHead1;
           
        ListNode* pMerge = pHead1->val <= pHead2->val ? pHead1 : pHead2;
        ListNode* p1 = pHead1->val <= pHead2->val ? pHead1 : pHead2;
        ListNode* p2 = pHead1->val > pHead2->val ? pHead1 : pHead2;
        ListNode* p1Next = nullptr;
        ListNode* p2Next = nullptr;
        while(p1!=nullptr && p2!=nullptr)
        {
            p1Next = p1->next;
            p2Next = p2->next;
            while(p1Next!=nullptr && !(p2->val>=p1->val && p2->val<p1Next->val))
            {
                p1 = p1Next;
                p1Next = p1->next;
            }
                
            p1->next = p2;
            p2->next = p1Next;
            p1=p2;
            p2 = p2Next;
        }
        return pMerge;
    }
};
           

2.遞歸

寫出來代碼非常簡潔，連結清單的問題似乎都可以用遞歸來解決。

• 終止條件，某一個連結清單為空時，直接傳回另一個。
• 目前函數 确定 兩個連結清單中的頭元素，
• 該頭元素的next 設定為 遞歸後函數的傳回值。
• 遞歸輸入參數為，除目前函數判斷出的首節點的其他節點。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==nullptr) return pHead2;
        if(pHead2==nullptr) return pHead1;
        
        ListNode* mergedHead = nullptr;
        if(pHead1->val <= pHead2->val)
        {            
            mergedHead = pHead1;
            mergedHead->next = Merge(pHead1->next, pHead2);
        }
        else
        {
            mergedHead = pHead2;
            mergedHead->next = Merge(pHead2->next, pHead1);
        }
        return mergedHead;
    }
};