[300 Bài Code Thiếu Nhi] Merge Two Sorted Lists – Python

Mô tả bài toán

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.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

Giải pháp

Để giải quyết bài toán này, trước hết ta chuẩn bị 1 biến dummy để lưu kết quả và 1 biến curr tham chiếu từ dummy làm biến trung gian. Thực hiện chạy vòng lặp cho đến khi list1 hoặc list2 rỗng.

Nếu giá trị note hiện tại của list1 lớn hơn giá trị note hiện tại của list2 thì thực hiện lưu giá trị list2 vào curr và trỏ list2 tới note tiếp theo. Ngược lại, nếu giá trị note hiện tại của list2 lớn hơn giá trị note hiện tại của list1 thì thực hiện lưu giá trị list1 vào curr và trỏ list1 tới note tiếp theo. Sau đó trỏ curr tới note tiếp theo và tiếp tục vòng lặp.

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        dummy = ListNode(0)
        curr  = dummy
        while list1 and list2:
            if list1.val > list2.val:
                curr.next = list2
                list2 = list2.next
            else:
                curr.next = list1
                list1 = list1.next
            curr = curr.next
            
        curr.next = list1 or list2
                
        return dummy.next

You need to login in order to like this post: click here