合并兩個排序的鏈表

合并兩個排序的鏈表 一、題目要求

輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。

二、我的思路

1、比較兩個鏈表的頭結(jié)點(diǎn)大小，哪個小就將其作為新鏈表的頭結(jié)點(diǎn)；
2、依次比較兩個鏈表節(jié)點(diǎn)的大小，將一個鏈表合并到另一個鏈表中；
3、合并完之后，剩余部分合并到新鏈表最后；

我的代碼 /* 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 == NULL) return pHead2; if(pHead2 == NULL) return pHead1; ListNode *head = NULL; if(pHead1->val <= pHead2->val){ head = pHead1; pHead1 = pHead1->next; } else{ head = pHead2; pHead2 = pHead2->next; } ListNode *p = head; while(pHead1 && pHead2){ if(pHead1->val <= pHead2->val){ p->next = pHead1; pHead1 = pHead1->next; } else{ p->next = pHead2; pHead2 = pHead2->next; } p = p->next; } if(pHead1) p->next = pHead1; else if(pHead2) p->next = pHead2; return head; } };