Merge Two Sorted Lists

Q: Độ phức tạp thời gian của việc gộp hai danh sách đã sắp xếp là bao nhiêu?

Độ phức tạp là O(L1 + L2) : mỗi lần so sánh sẽ đưa một nút vào, và không có nút nào được đưa vào hai lần. Với các đối tượng nút, thao tác gộp cần thêm O(1) bộ nhớ vì chỉ thay đổi các liên kết. Với các mảng được dùng ở đây, mảng liên kết dùng chung cần O(L1 + L2) bộ nhớ.

DễDanh sách liên kết Hai con trỏ

+10

Bạn nhận được hai danh sách liên kết đơn, mỗi danh sách được lưu trong hai mảng có cùng độ dài. Trong danh sách thứ nhất, nút i chứa giá trị values1[i] và liên kết đến nút next1[i]. Danh sách thứ hai hoạt động tương tự với next2 và values2. Trong cả hai danh sách, -1 đánh dấu điểm kết thúc và nút đầu là nút 0. Các nút không được lưu theo thứ tự trong danh sách, vì vậy hãy lần theo các liên kết.

Mỗi danh sách được sắp xếp theo thứ tự không giảm dọc theo các liên kết. Hãy gộp hai danh sách thành một danh sách đã sắp xếp rồi trả về các giá trị theo thứ tự.

Hàm

mergeTwoLists(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: chỉ số của nút mà mỗi nút trong danh sách đầu tiên trỏ tới, hoặc -1 nếu đó là nút cuối cùng
values1integer-array: giá trị mà mỗi nút trong danh sách đầu tiên lưu giữ
next2integer-array: chỉ số của nút mà mỗi nút trong danh sách thứ hai liên kết đến, hoặc -1 nếu đó là nút cuối cùng
values2integer-array: giá trị của từng nút trong danh sách thứ hai
Trả vềinteger-array: các giá trị trong danh sách đã gộp, theo thứ tự

Ràng buộc

1 ≤ L1 ≤ 2000, trong đó L1 là độ dài của next1 và values1.
1 ≤ L2 ≤ 2000, trong đó L2 là độ dài của next2 và values2.
-1000 ≤ values1[i], values2[j] ≤ 1000
Mỗi phần tử của next1 là -1 hoặc chỉ số nút của danh sách thứ nhất, và mỗi phần tử của next2 là -1 hoặc chỉ số nút của danh sách thứ hai.
Bắt đầu từ nút 0, mỗi danh sách đi qua từng nút đúng một lần rồi đến -1. Không có chu trình.
Dọc theo các liên kết, mỗi danh sách được sắp xếp theo thứ tự không giảm.

Ví dụ

Đầu vào: next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
Đầu ra: [1, 2, 3, 4, 6, 7, 9]
Giải thích: Theo các liên kết, danh sách thứ nhất đi qua các nút 0, 2, 1 và đọc được 1, 4, 6; danh sách thứ hai đọc được 2, 3, 7, 9. Mỗi lần lấy phần tử đầu nhỏ hơn sẽ cho kết quả 1, 2, 3, 4, 6, 7, 9.

Đầu vào: next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
Đầu ra: [-3, 0, 0, 5]
Giải thích: Danh sách đầu tiên gồm -3, 0, 5, còn danh sách thứ hai chỉ có giá trị 0. Cả hai giá trị 0 đều được giữ lại trong kết quả, nên kết quả có bốn giá trị.

Đầu vào: next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
Đầu ra: [1, 2, 3, 8, 10]
Giải thích: Các giá trị trong danh sách thứ hai là 1, 2, 3, tất cả đều nhỏ hơn 8, giá trị bắt đầu danh sách thứ nhất. Toàn bộ danh sách thứ hai đứng trước, rồi đến 8, 10.

Câu hỏi mở rộng

Bạn có thể gộp k danh sách đã sắp xếp trong thời gian O(N log k), với N là tổng số nút không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Cả hai danh sách đều đã được sắp xếp, nên giá trị nhỏ nhất còn lại luôn nằm ở đầu một trong hai danh sách. So sánh hai phần tử ở đầu, nối phần tử nhỏ hơn vào kết quả rồi tiến thêm một bước trong danh sách đó. Sắp xếp tất cả N = L1 + L2 giá trị cũng được, nhưng cách này bỏ qua thứ tự đó và tốn O(N log N).

Đưa tất cả giá trị vào một mảng rồi sắp xếp

Ý tưởng

Danh sách sau khi gộp là phiên bản đã sắp xếp của tất cả giá trị N, vì vậy hãy sao chép cả hai mảng giá trị vào một mảng rồi sắp xếp mảng đó. Thứ tự các nút bên trong các mảng không quan trọng, vì thao tác sắp xếp sẽ đặt mọi giá trị vào đúng vị trí. Với N ≤ 4000, cách này đủ nhanh, nhưng sắp xếp cần O(N log N) phép so sánh, trong khi thao tác gộp chỉ cần tối đa N-1 phép so sánh và không hề chạm đến liên kết, kỹ năng mà bài toán này kiểm tra.

Thuật toán

Sao chép values1 và values2 vào một mảng.
Sắp xếp mảng theo thứ tự không giảm.
Trả về mảng đó.

def mergeTwoLists(next1, values1, next2, values2):
    # Sorting puts every value in its place without following a single link.
    return sorted(values1 + values2)

Nối các nút phía sau nút đầu giả

Ý tưởng

Con trỏ ở đây là chỉ số nút. Để nối các nút của cả hai danh sách thành một chuỗi, hãy đánh số chúng chung: nút j của danh sách 2 trở thành nút L1+j, các liên kết của nó cũng được dịch chuyển tương ứng. Một nút giả, mang số L1+L2, đứng trước kết quả.

Giữ a và b trỏ đến nút chưa dùng đầu tiên của mỗi danh sách, còn tail trỏ đến cuối chuỗi đã gộp. Mỗi bước nối tail với nút đầu có giá trị nhỏ hơn, rồi dịch chuyển con trỏ đó và tail về phía trước. Khi một danh sách hết nút, phần còn lại của danh sách kia đã được sắp xếp và liên kết sẵn, nên chỉ cần một phép gán để nối phần đó vào. Trong ví dụ đầu tiên, danh sách 2 trở thành các nút từ 3 đến 6. Sau các nút 0, 3, 6, 2, 1, danh sách 1 đã hết và link[tail] = 4 nối các nút 7, 9.

Mỗi nút được nối tối đa một lần: thời gian O(N). Mảng liên kết dùng chung tốn O(N) bộ nhớ, trong khi các đối tượng nút không cần bộ nhớ nào.

Thuật toán

Tạo một mảng liên kết: next1, rồi đến next2 sau khi dịch thêm L1 (giữ nguyên -1), rồi đến -1 cho nút giả L1+L2. Tạo các giá trị tương ứng.
Đặt a = 0, b = L1 và tail trỏ đến nút giả.
Trong khi cả a và b đều không phải -1, liên kết tail với nút nhỏ hơn (a nếu bằng nhau), tiến con trỏ đó lên một bước rồi chuyển tail đến nút đó.
Liên kết tail với nút nào trong a và b không phải -1.
Đi từ link[dummy] đến -1 và thu thập các giá trị.

def mergeTwoLists(next1, values1, next2, values2):
    n1 = len(next1)
    n2 = len(next2)
    # One node space: list 2's node j becomes node n1 + j, and node n1 + n2 is a
    # dummy that sits in front of the merged list.
    link = list(next1) + [j + n1 if j != -1 else -1 for j in next2] + [-1]
    value = list(values1) + list(values2)
    dummy = n1 + n2
    tail = dummy  # the last node of the merged list so far
    a = 0  # the first unused node of list 1
    b = n1  # the first unused node of list 2
    while a != -1 and b != -1:
        if value[a] <= value[b]:
            link[tail] = a  # splice a in after the tail
            a = link[a]
        else:
            link[tail] = b  # splice b in after the tail
            b = link[b]
        tail = link[tail]
    # One list ran out. The rest of the other one is sorted and linked already.
    link[tail] = a if a != -1 else b
    merged = []
    node = link[dummy]
    while node != -1:
        merged.append(value[node])
        node = link[node]
    return merged

Lỗi thường gặp và trường hợp biên

Gộp các mảng theo thứ tự chỉ số. Các nút được lưu theo thứ tự xáo trộn, vì vậy bản thân values1 không được sắp xếp: trong ví dụ đầu tiên, nó là [1, 6, 4]. Chỉ đường đi bắt đầu từ nút 0 mới được sắp xếp.
Bỏ quên các phần tử còn lại. Khi một danh sách hết phần tử, vòng lặp dừng lại. Nếu bỏ phần còn lại của danh sách kia, bạn sẽ làm mất các giá trị lớn nhất: 7, 9 trong ví dụ đầu tiên.
Di chuyển sai con trỏ hoặc di chuyển cả hai. Chỉ danh sách có nút được lấy mới tiến lên.
Nhầm lẫn hai cách đánh số. Nút 2 của danh sách 2 không phải là nút 2 của danh sách 1. Dịch chỉ số và liên kết của danh sách 2 thêm L1, và giữ nguyên -1.

Câu hỏi thường gặp3

Độ phức tạp thời gian của việc gộp hai danh sách đã sắp xếp là bao nhiêu?

Độ phức tạp là O(L1 + L2): mỗi lần so sánh sẽ đưa một nút vào, và không có nút nào được đưa vào hai lần. Với các đối tượng nút, thao tác gộp cần thêm O(1) bộ nhớ vì chỉ thay đổi các liên kết. Với các mảng được dùng ở đây, mảng liên kết dùng chung cần O(L1 + L2) bộ nhớ.

Tại sao nên dùng nút giả khi gộp các danh sách liên kết?

Nếu không có nó, bạn cần viết code riêng cho nút đầu tiên của kết quả vì chưa có nút cuối để nối nó vào sau. Nút giả đóng vai trò là nút đầu, nên nút đầu tiên được nối theo cách giống như mọi nút khác. Cuối cùng, bạn trả về nút tiếp theo của nút giả và nút giữ chỗ sẽ biến mất.

Bạn nên gộp hai danh sách đã sắp xếp bằng đệ quy hay lặp?

Phiên bản đệ quy khá ngắn: phần đầu nhỏ hơn nối với kết quả trộn của tất cả phần còn lại. Nhưng phiên bản này dùng một khung ngăn xếp cho mỗi nút, vì vậy danh sách có vài nghìn nút có thể làm tràn ngăn xếp trong một số ngôn ngữ. Vòng lặp lặp dùng con trỏ đuôi thực hiện cùng công việc mà chỉ cần không gian ngăn xếp cố định.

def mergeTwoLists(next1, values1, next2, values2):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

next1 = [2, -1, 1]
values1 = [1, 6, 4]
next2 = [3, 2, -1, 1]
values2 = [2, 7, 9, 3]

Đầu ra mong đợi

[1, 2, 3, 4, 6, 7, 9]