Hợp nhất K danh sách liên kết đã sắp xếp trong Java

Cho K danh sách liên kết có kích thước khác nhau, đã được sắp xếp. Nhiệm vụ là hợp nhất chúng thành một danh sách kết quả cũng được sắp xếp theo thứ tự.

Ví dụ minh họa

Đầu vào: k = 3

list[0] = 11 → 15 → 17
list[1] = 2 → 3 → 26 → 39
list[2] = 4 → 8 → 10

Đầu ra: Danh sách hợp nhất: 2 → 3 → 4 → 8 → 10 → 11 → 15 → 17 → 26 → 39 → null

Giải thích: So sánh đầu các danh sách bằng Comparator và hợp nhất theo thứ tự.

Đầu vào: k = 2

list[0] = 1 → 4 → 5
list[1] = 2 → 3 → 6 → 8

Đầu ra: Danh sách hợp nhất: 1 → 2 → 3 → 4 → 5 → 6 → 8 → null

Phương pháp tiếp cận

• Nhập số lượng danh sách K
• Khởi tạo lớp Node cho danh sách liên kết
• Khởi tạo các node theo thứ tự sắp xếp, truyền head vào mergeLists(list, k)
• Sử dụng PriorityQueue với Comparator so sánh giá trị node
• Thêm tất cả head vào queue
• Lặp lấy node nhỏ nhất, nối vào danh sách kết quả, thêm node.next vào queue nếu có
• Trả về head của danh sách đã hợp nhất

Ví dụ mã Java

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Node {
    int data;
    Node next;
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class testClass {
    public static Node mergeLists(Node[] list, int k) {
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(
            Comparator.comparingInt(a -> ((Node) a).data));
        priorityQueue.addAll(Arrays.asList(list).subList(0, k));
        
        Node head = null, last = null;
        while (!priorityQueue.isEmpty()) {
            Node min = priorityQueue.poll();
            if (head == null) {
                head = last = min;
            } else {
                last.next = min;
                last = min;
            }
            if (min.next != null) {
                priorityQueue.add(min.next);
            }
        }
        return head;
    }
    
    public static void main(String[] s) {
        int k = 3;
        Node[] list = new Node[k];
        list[0] = new Node(11);
        list[0].next = new Node(15);
        list[0].next.next = new Node(17);
        list[1] = new Node(2);
        list[1].next = new Node(3);
        list[1].next.next = new Node(26);
        list[1].next.next.next = new Node(39);
        list[2] = new Node(4);
        list[2].next = new Node(8);
        list[2].next.next = new Node(10);
        
        System.out.println("The merged list is-->");
        Node head = mergeLists(list, k);
        while (head != null) {
            System.out.print(head.data + ">> ");
            head = head.next;
        }
        System.out.print("null");
    }
}

Đầu ra

The merged list is--> 2>> 3>> 4>> 8>> 10>> 11>> 15>> 17>> 26>> 39>> null