DAY16 Merge Two Sorted Lists

第 11 屆 iThome 鐵人賽

DAY 16

自我挑戰組

刷題記錄與人生分享系列第 16 篇

11th鐵人賽 leetcode c javascript

keyhouse12

2019-09-17 10:45:22

1406 瀏覽

分享至

題目:

https://leetcode.com/problems/merge-two-sorted-lists/
合併2個排序好的鏈結串列，按排序大小回傳一個新的鏈結串列。

解題思路:

宣告2個指標紀錄2個連結串列的首節點，且當2個指標不為空時並相互判斷其值大小，temp、result指標紀錄暫時及結果，以此循環當其中一個連結串列為空時，則直接合併另一個已排序好的連結串列。

C版本:

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *temp;
    struct ListNode *result;
    
    if(l1 == NULL && l2 == NULL)
    {
        return NULL;
    }
    else if(l1 == NULL && l2 != NULL)
    {
        return l2;
    }
    else if(l1 != NULL && l2 == NULL)
    {
        return l1;
    }
    
    if(l1 -> val <= l2 -> val)
    {
        temp = l1;
        l1 = l1 -> next;
    }
    else
    {
        temp = l2;
        l2 = l2 -> next;
    }
    
    result = temp;
    while(l1 != NULL && l2 != NULL)
    {
        if (l1->val<=l2->val) {
            temp->next=l1;
            l1=l1->next;
        }
        else {
            temp->next=l2;
            l2=l2->next;
        }  
        temp=temp->next;
    }
    if(l1) {
        temp->next=l1;
    }
    else if(l2){
        temp->next=l2;
    }
    
    return result;
}

Javascript版本:

var mergeTwoLists = function(l1, l2) {
    var temp = new ListNode(0);
    var result = new ListNode(0);
    
    if(l1 == null && l2 == null)
    {
        return null;
    }
    else if(l1 == null && l2 != null)
    {
        return l2;
    }
    else if(l1 != null && l2 == null)
    {
        return l1;
    }
    
    if(l1.val <= l2.val)
    {
        temp = l1;
        l1 = l1.next;
    }
    else
    {
        temp = l2;
        l2 = l2.next;
    }
    
    result = temp;
    while(l1 != null && l2 != null)
    {
        if (l1.val<=l2.val) {
            temp.next = l1;
            l1 = l1.next;
        }
        else {
            temp.next = l2;
            l2 = l2.next;
        }  
        temp=temp.next;
    }
    if(l1) {
        temp.next = l1;
    }
    else if(l2){
        temp.next = l2;
    }
    
    return result;
};