題目描述
輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表纵东，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則歼捏。
思路
- 聲明 p, q 兩個(gè)結(jié)點(diǎn)指針，分別指向兩個(gè)鏈表的當(dāng)前結(jié)點(diǎn)而涉。
- 聲明 newHead, 新鏈表的頭指針著瓶，newPnow 指向新鏈表的當(dāng)前結(jié)點(diǎn)。
- p q 兩個(gè)結(jié)點(diǎn)指向的值互相比較啼县，新鏈表的當(dāng)前結(jié)點(diǎn)指向那個(gè)比較小的材原，之后互相向前移動(dòng)。
- 當(dāng)有一個(gè)鏈表為空季眷，直接將新鏈表當(dāng)前結(jié)點(diǎn)的 next 指針指向另外一個(gè)鏈表余蟹，后面本身就是已經(jīng)連著的。
代碼
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
ListNode* p, *q, *newHead = NULL, *newPNow;
p = pHead1;
q = pHead2;
if(pHead1 == NULL)
return pHead2;
else if(pHead2 == NULL)
return pHead1;
while(p != NULL && q != NULL)
{
if(p->val >= q->val)
{
if(newHead == NULL)
{
newHead = q;
newPNow = q;
q = q->next;
}
else
{
newPNow->next = q;
newPNow = q;
q = q->next;
}
}
else
{
if(newHead == NULL)
{
newHead = p;
newPNow = p;
p = p->next;
}
else
{
newPNow->next = p;
newPNow = p;
p = p->next;
}
}
}
if(p == NULL)
{
newPNow->next = q;
}
else if(q == NULL)
{
newPNow->next = p;
}
return newHead;
}
};
