其實合并兩個有序連結清單:最主要的就是記憶體配置設定,這是使用的是堆記憶體,自己控制開辟和釋放
周遊式:
代碼:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *head = new ListNode(0);
ListNode *end = head;
while(l1 && l2){
if(l1->val < l2 ->val){
ListNode *tmp = new ListNode(l1->val);
end->next = tmp;
end = tmp;
l1= l1->next;
}
else
{
ListNode *tmp = new ListNode(l2->val);
end->next = tmp;
end = tmp;
l2= l2->next;
}
}
while(l1)
{
ListNode *tmp = new ListNode(l1->val);
end->next = tmp;
end = tmp;
l1= l1->next;
}
while(l2)
{
ListNode *tmp = new ListNode(l2->val);
end->next = tmp;
end = tmp;
l2= l2->next;
}
return head->next;
}
/*
ListNode* MergeTwoLists(ListNode* l1, ListNode* l2){
if(l1->)
}*/
};
遞歸式:
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == nullptr)
return l2;
if(l2 == nullptr)
return l1;
ListNode * CurrNode = nullptr;
if(l1->val < l2->val){
CurrNode = l1;
CurrNode->next = mergeTwoLists(l1->next,l2);
}
else{
CurrNode = l2;
CurrNode->next = mergeTwoLists(l1,l2->next);
}
return CurrNode;
}
};