Leetcode 21. Merge Two Sorted Lists

題目要求將兩個已排序的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;
        } 
    }
};

Python

C++

相關