題目要求將兩個已排序的linked lists合併,且所產生的新list必須由原有的節點(node)所構成。
Python
Linked List是一個很常見的資料結構,資料與資料連接的方式是單向的,
通常從第一個節點(node)往後連接到最後一個節點(node)。
每個節點上會存放一個資料以及連結(link),
每個連結會指向到下一個節點的位置(記憶體位址)。
最後一個節點除了儲存資料以外,因為連結沒有東西了,所以會給定空值。
class Solution:
def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
head=ListNode(None)
prev=head
while l1 and l2:
if l1.val<=l2.val: #值較小,帶入prev.next
prev.next=l1
l1=l1.next #移到下一個節點
else:
prev.next=l2
l2=l2.next
prev=prev.next #prev移到自己的下一個節點
if l1 ==None: #l1弄光,prev.next帶入l2
prev.next=l2
elif l2==None:
prev.next=l1
return head.next
C++
方法一
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0); // 儲存結果的ListNode
ListNode* tmp=&dummy; // Node目前位置
while(l1&&l2)
{
// l1,l2較小的數加入tmp
if(l1->val<=l2->val)
{
tmp->next = l1;
l1 = l1->next;
}
else
{
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
}
tmp->next = (l1? l1:l2); //l1,l2剩下的Node加到tmp
return dummy.next;
}
};
方法二 : 遞歸
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1||!l2) return l1?l1:l2;
//l1,l2較小的數透過遞歸向下求出解
if(l1->val<=l2->val)
{
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
else
{
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
};