به ما تعداد K لیست پیوندی داده شده که هر کدام جداگانه مرتب هستند. ما می خواهیم از این لیست های مرتب، یک لیست مرتب واحد بسازیم و همه آن ها را ادغام کنیم.

مثال:

به طور مثال داریم:

List 1: -->1-->5
List 2: -->4-->8
List 3: -->4-->6-->9
List 4: -->2-->7-->10
Merged Linked List: 
-->1-->2-->4-->4-->5-->6-->7-->8-->9-->10

شیوه ما در این مطلب آموزشی از وبسایت اوپن مایند، ادغام لیست های جداگانه به وسیله صف اولویت دار است.

الگوریتم ادغام:

الگوریتم کار به طریق زیر بیان می شود:

1. یک صف اولویت دار ایجاد می کنیم.
2. گره اول همه K لیست پیوندی را به صف اولویت دار اضافه می کنیم.
3. تا زمانی که صف اولویت دار خالی نشده است کار های زیر را انجام می دهیم:
   1. یک گره را از صف اولویت دار خارج می کنیم (گره با کمترین مقدار خارج می شود).
   2. اگر این گره خارج شده یک گره بعدی دارد، بعدی آن را به صف اولویت دار وارد می کنیم.
   3. گره خارج شده از صف را به انتهای لیست پیوندی نهایی (ادغام شده) اضافه می کنیم.
4. لیست نهایی (ادغام شده) را بر می گردانیم.

توجه:

در کد جاوای زیر، تابع مقایسه گر کلاس صف اولویت دار را بازنویسی کرده ایم تا بتواند بر اساس ساختار گره که توسط خودمان تعریف شده، مقایسه بین گره ها را انجام دهد و اولویت را به گره ای با کمترین مقدار بدهد.

کد جاوای ادغام K لیست پیوندی مرتب با صف اولویت دار:

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

public class MergeKSortedLinkedList {

    static ListNode merge(ListNode[] heads) {
        ListNode resultHead = null;
        ListNode current = null;

        PriorityQueue < ListNode > pq = new PriorityQueue < > (new Comparator < ListNode > () {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.data - o2.data;
            }
        });

        //insert all heads into priority queue
        for (int i = 0; i < heads.length; i++) {
            if (heads[i] != null) {
                pq.offer(heads[i]);
            }
        }

        while (!pq.isEmpty()) {
            //extract the min from priority queue
            ListNode node = pq.poll();

            //add it to result Head
            if (resultHead == null) {
                resultHead = node;
                current = node;
            } else {
                current.next = node;
                current = current.next;
            }

            //add next List Node to priority queue
            if (node.next != null) {
                pq.add(node.next);
            }
        }
        return resultHead;
    }
    static class ListNode {
        int data;
        ListNode next;

        public ListNode(int data) {
            this.data = data;
        }
    }

    static void print(ListNode node) {
        ListNode current = node;
        while (current != null) {
            System.out.print("-->" + current.data);
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(5);
        print(list1);

        ListNode list2 = new ListNode(4);
        list2.next = new ListNode(8);
        print(list2);

        ListNode list3 = new ListNode(4);
        list3.next = new ListNode(6);
        list3.next.next = new ListNode(9);
        print(list3);

        ListNode list4 = new ListNode(2);
        list4.next = new ListNode(7);
        list4.next.next = new ListNode(10);
        print(list4);

        ListNode[] heads = new ListNode[] {
            list1,
            list2,
            list3,
            list4
        };
        ListNode result = merge(heads);
        System.out.println("Merged Linked List: ");
        print(result);
    }
}

خروجی اجرای کد بالا به شکل زیر است:

-->1-->5
-->4-->8
-->4-->6-->9
-->2-->7-->10
Merged Linked List: 
-->1-->2-->4-->4-->5-->6-->7-->8-->9-->10