Bài 21 Leetcode: Merge Two Sorted Lists

Đề bài:

Cho đầu của hai danh sách liên kết đã được sắp xếp là list1 và list2.

Hợp nhất hai danh sách thành một danh sách được sắp xếp. Danh sách mới được tạo bằng cách nối các nút của hai danh sách ban đầu.

Trả về đầu của danh sách liên kết đã được hợp nhất.

Ví dụ 1:

Merge Two Sorted Lists
Merge Two Sorted Lists
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Ví dụ 2:

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

Ví dụ 3:

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

Ràng buộc:

  • Số lượng nút trong cả hai danh sách nằm trong khoảng [0, 50].
  • -100 <= Node.val <= 100
  • Cả list1 và list2 được sắp xếp theo thứ tự không giảm.

Giải thích thuật toán bằng C++

class Solution {
 public:
  ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if (!list1 || !list2)
      return list1 ? list1 : list2;
    if (list1->val > list2->val)
      swap(list1, list2);
    list1->next = mergeTwoLists(list1->next, list2);
    return list1;
  }
};

Đây là một phương thức trong một lớp được gọi là `Solution`. Phương thức này được sử dụng để hợp nhất hai danh sách liên kết đã được sắp xếp thành một danh sách liên kết mới.

Dưới đây là cách thuật toán hoạt động:

1. Phương thức `mergeTwoLists` nhận đầu vào là hai con trỏ `list1` và `list2`, đại diện cho hai danh sách liên kết đã được sắp xếp.

2. Kiểm tra nếu `list1` hoặc `list2` là null (không tồn tại), tức là một trong hai danh sách rỗng. Trong trường hợp này, ta trả về danh sách không rỗng nếu có, hoặc danh sách rỗng nếu cả hai danh sách đều rỗng.

3. Kiểm tra nếu giá trị của nút đầu tiên trong `list1` lớn hơn giá trị của nút đầu tiên trong `list2`. Nếu điều này xảy ra, ta hoán đổi `list1` và `list2` để đảm bảo `list1` luôn có giá trị nhỏ hơn hoặc bằng giá trị của `list2`.

4. Gán con trỏ `next` của `list1` bằng kết quả của việc hợp nhất danh sách tiếp theo giữa `list1->next` và `list2`. Điều này sẽ đệ quy gọi phương thức `mergeTwoLists` để tiếp tục hợp nhất các nút tiếp theo của `list1` và `list2`.

5. Trả về con trỏ `list1`, đại diện cho danh sách liên kết đã được hợp nhất.

Thuật toán này sử dụng đệ quy để hợp nhất hai danh sách liên kết đã được sắp xếp. Ta so sánh giá trị của nút đầu tiên trong `list1` và `list2`, và ta luôn đảm bảo rằng `list1` có giá trị nhỏ hơn hoặc bằng giá trị của `list2`. Sau đó, ta gán `list1->next` bằng kết quả của việc hợp nhất danh sách tiếp theo giữa `list1->next` và `list2`. Quá trình này được lặp lại cho đến khi một trong hai danh sách trở thành null, và ta trả về danh sách đã được hợp nhất.

Giải thích thuật toán bằng Java

class Solution {
  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null || list2 == null)
      return list1 == null ? list2 : list1;
    if (list1.val > list2.val) {
      ListNode temp = list1;
      list1 = list2;
      list2 = temp;
    }
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    if not list1 or not list2:
      return list1 if list1 else list2
    if list1.val > list2.val:
      list1, list2 = list2, list1
    list1.next = self.mergeTwoLists(list1.next, list2)
    return list1

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.