Skip to content

LeetCode: 21-Merge Two Sorted Lists 解題紀錄

Last Updated on 2021-01-31 by Clay

題目

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

題目輸入兩個已經排序過的 Linked List，而我們要將其『合併』，並回傳同樣排序過的 Linked List。

解題思路

這題我的解題方式也是滿暴力的：新建一個新的 Linked Lis，然後比較輸入的兩個 Linked List，將新的先指向較小的元素，然後依此類推，直到其中一個 Linked List 指向 NULL 為止，便把還有元素的 Linked List 直接串到新的 Linked List 上。

在 C++ 的效果還行，但這個辦法在 Python 上又非常慢了 @@


C++ 程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // Init
        ListNode* currentNode_1 = new ListNode();
        ListNode* currentNode_2 = new ListNode();
        ListNode* head = new ListNode();
        ListNode* current = new ListNode();
        
        // Point
        currentNode_1->next = l1;
        currentNode_2->next = l2;
        current->next = head;
        
        // Merge the bigger one
        while (currentNode_1->next != NULL && currentNode_2->next != NULL) {
            if (currentNode_1->next->val <= currentNode_2->next->val) {
                current->next->next = currentNode_1->next;
                current->next = current->next->next;
                currentNode_1->next = currentNode_1->next->next;
            }
            else {
                current->next->next = currentNode_2->next;
                current->next = current->next->next;
                currentNode_2->next = currentNode_2->next->next;            
            }
        }
        
        // Merge the remaining link list
        if (currentNode_1->next == NULL) {
            current->next->next = currentNode_2->next;
        }
        else {
            current->next->next = currentNode_1->next;
        }
        
        return head->next;
    }
};


Python 程式碼

# 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, l1: ListNode, l2: ListNode) -> ListNode:
        # Init
        currentNode_1 = ListNode(next=l1)
        currentNode_2 = ListNode(next=l2)
        head = ListNode()
        current = ListNode(next=head)
        
        # Merge
        while currentNode_1.next != None and currentNode_2.next != None:
            if currentNode_1.next.val <= currentNode_2.next.val:
                current.next.next = currentNode_1.next
                current.next = current.next.next
                currentNode_1.next = currentNode_1.next.next
            else:
                current.next.next = currentNode_2.next
                current.next = current.next.next
                currentNode_2.next = currentNode_2.next.next
            
        if currentNode_1.next == None:
            current.next.next = currentNode_2.next;
        else:
            current.next.next = currentNode_1.next;
        
        return head.next


References

Tags:

Leave a Reply