ภาพรวมปัญหา
ได้รับ K ลิงก์ลิสต์ที่จัดเรียงแล้วแต่ละอัน ต้องรวมเป็นลิงก์ลิสต์เดียวที่จัดเรียงตามลำดับ
ตัวอย่าง
ตัวอย่างที่ 1
Input: k = 3
list[0]: 11 → 15 → 17
list[1]: 2 → 3 → 26 → 39
list[2]: 4 → 8 → 10
Output: 2 → 3 → 4 → 8 → 10 → 11 → 15 → 17 → 26 → 39 → null
ตัวอย่างที่ 2
Input: k = 2
list[0]: 1 → 4 → 5
list[1]: 2 → 3 → 6 → 8
Output: 1 → 2 → 3 → 4 → 5 → 6 → 8 → null
แนวทางการแก้ปัญหา
- ใช้ PriorityQueue (Min-Heap) เพื่อเก็บหัวของแต่ละลิสต์
- Comparator เรียงตามค่า data ของ Node
- นำ Node ที่มีค่าน้อยที่สุดออกจาก Queue ต่อท้ายผลลัพธ์
- หาก Node นั้นมี next ให้เพิ่ม next เข้า Queue
- ทำซ้ำจน Queue ว่าง
ตัวอย่างโค้ด Java
import java.util.*;
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 pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.data));
pq.addAll(Arrays.asList(list).subList(0, k));
Node head = null, last = null;
while (!pq.isEmpty()) {
Node min = pq.poll();
if (head == null) head = last = min;
else { last.next = min; last = min; }
if (min.next != null) pq.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");
}
} ผลลัพธ์
The merged list is--> 2>> 3>> 4>> 8>> 10>> 11>> 15>> 17>> 26>> 39>> null
