LeetCode #21 Merge Two Sorted Lists 合併兩個已排序的鏈結串列

LeetCode題目翻譯

英文原文如下

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

中文翻譯

給予你兩個已排序的鏈結串列的首個節點

將兩個串列合併成一個經排序的鏈結串列,該串列應通過前兩個串列的節點拼接在一起

回傳合併串列的首個節點

範例及題目限制

LeetCode#21 範例
LeetCode#21 題目

解題思路

第一種方法非常單純,先把兩個串列 head的值進行比較,小的那個設為起始點

接著對兩個listnode進行迭代比較,直到其中一個用完為止

合併串列的下一個節點就會直接指向剩的那個鏈結串列

C# 解決方案

方案1 – 迭代

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
        
        if(list1 == null){ return list2;}
        if(list2 == null){ return list1;}
 
        ListNode resNode = new ListNode();
        
        //init
        if(list1.val>list2.val)
        {
            resNode.val = list2.val;
            list2 = list2.next;
        }
        else
        {
            resNode.val = list1.val;
            list1 = list1.next;
        }
        
        ListNode lastNode = resNode;
        
        //iterate to one listNode next is null
        while(list1!=null && list2!=null)
        {
            ListNode nowNode = new ListNode();
            if(list1.val>list2.val)
            {
                nowNode.val = list2.val;
                list2 = list2.next;
            }
            else
            {
                nowNode.val = list1.val;
                list1 = list1.next;
            }
            
            lastNode.next = nowNode;
            lastNode = nowNode;
        }
        
        //one linked list will have some remain node
        if(list1!=null)
        {
            lastNode.next = list1;
        }
        else
        {
            lastNode.next = list2;
        }
    
        return resNode;
    }
}

第二種則是用遞迴的寫法

通過不斷的呼叫 recursion 這支程式進行排序的動作

寫起來比迭代來的簡單多了

既不需要另外新增一個回傳串列,也不需要判斷先跑完的串列

⭐方案2 – 遞迴

public class Solution {
    public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
        return recursion(list1,list2);
    }
    
    public ListNode recursion(ListNode l1, ListNode l2)
    {
        if(l1 == null)
        {
            return l2;  
        }
        if(l2==null)
        {
            return l1;
        }
        if(l1.val>l2.val)
        {
            return new ListNode(l2.val,recursion(l2.next, l1));
        }
        else
        {
            return new ListNode(l1.val, recursion(l2, l1.next));  
        }
    }
}

(為節省版面,把Definition省略了,不影響)

Java解決方案

方案1 – 迭代

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){ return list2;}
        if(list2 == null){ return list1;}
 
        ListNode resNode = new ListNode();
        
        //init
        if(list1.val>list2.val)
        {
            resNode.val = list2.val;
            list2 = list2.next;
        }
        else
        {
            resNode.val = list1.val;
            list1 = list1.next;
        }
        
        ListNode lastNode = resNode;
        
        //iterate to one listNode next is null
        while(list1!=null && list2!=null)
        {
            ListNode nowNode = new ListNode();
            if(list1.val>list2.val)
            {
                nowNode.val = list2.val;
                list2 = list2.next;
            }
            else
            {
                nowNode.val = list1.val;
                list1 = list1.next;
            }
            
            lastNode.next = nowNode;
            lastNode = nowNode;
        }
        
        //one linked list will have some remain node
        if(list1!=null)
        {
            lastNode.next = list1;
        }
        else
        {
            lastNode.next = list2;
        }
    
        return resNode;
    }
}

⭐方案2 – 遞迴

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        return recursion(list1,list2);
    }
    
    
    public ListNode recursion(ListNode l1, ListNode l2)
    {
        if(l1 == null)
        {
        return l2;  
        }
        if(l2==null)
        {
            return l1;
        }
        if(l1.val>l2.val)
        {
            return new ListNode(l2.val,recursion(l2.next, l1));
        }
        else
        {
            return new ListNode(l1.val, recursion(l2, l1.next));  
        }
    }
}

Python3 解決方案

方案1 – 迭代

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if(list1 == None): 
            return list2;
        if(list2 == None):
            return list1;
 
        resNode = ListNode();
        
        #init
        if(list1.val>list2.val):
            resNode.val = list2.val;
            list2 = list2.next;
        
        else:
            resNode.val = list1.val;
            list1 = list1.next;

        lastNode = resNode;
        
        #iterate to one listNode next is None
        while(list1!=None and list2!=None):
        
            nowNode = ListNode();
            if(list1.val>list2.val):
                nowNode.val = list2.val;
                list2 = list2.next;
            
            else:
                nowNode.val = list1.val;
                list1 = list1.next;
    
            lastNode.next = nowNode;
            lastNode = nowNode;

        #one linked list will have some remain node
        if(list1!=None):
            lastNode.next = list1;
        
        else:
            lastNode.next = list2;
    
        return resNode;

方案2– 遞迴

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        def recursion(l1, l2):
            if l1 == None:
                return l2;
            if l2 == None:
                return l1;
            
            if l1.val > l2.val:
                return ListNode(l2.val, recursion(l2.next, l1));
            else:
                return ListNode(l1.val, recursion(l2, l1.next));
            
        return recursion(list1, list2);

結論

🧡如果這篇文章有幫上你的一點點忙,那是我的榮幸

🧡可以的話,幫我的FaceBook 粉絲專頁按個讚,我會很感謝的

✅如有任何疑問,歡迎透過留言或messenger讓我知道 !

題目連結 : Merge Two Sorted Lists – LeetCode

最新文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *