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