รวมรายการที่เชื่อมโยง K ที่เรียงลำดับใน Java

เราได้รับรายการที่เชื่อมโยงของขนาดตัวแปรจำนวน K ซึ่งเรียงลำดับตามลำดับและเราต้องรวมรายการเข้ากับรายการผลลัพธ์ในลักษณะที่อาร์เรย์ผลลัพธ์ถูกจัดเรียงไม่เรียงลำดับและอาร์เรย์ผลลัพธ์จะถูกพิมพ์เป็นเอาต์พุตไปยัง ผู้ใช้

ให้เราเข้าใจด้วยตัวอย่าง:-

ป้อนข้อมูล −

int k =3;

list[0] =โหนดใหม่(11);

list[0].next =new Node(15);

list[0].next.next =new Node(17);

รายการ[1] =โหนดใหม่(2);

list[1].next =โหนดใหม่(3)

list[1].next.next =โหนดใหม่ (26);

list[1].next.next.next =โหนดใหม่ (39);

รายการ[2] =โหนดใหม่(4);

list[2].next =โหนดใหม่(8)

list[2].next.next =โหนดใหม่(10);

ผลผลิต −รายการที่รวมคือ-->

2>> 3>> 4>> 8>> 10>> 11>> 15>> 17>> 26>> 39>> null

คำอธิบาย −เราได้รับรายการเชื่อมโยงจำนวน K ซึ่งจัดเรียงตามลำดับ กระบวนการรวมประกอบด้วยการเปรียบเทียบส่วนหัวของรายการที่เชื่อมโยงโดยใช้ฟังก์ชันตัวเปรียบเทียบจาวาและรวมเข้าด้วยกันในอาร์เรย์ผลลัพธ์

ป้อนข้อมูล −

int k =2;

list[0] =โหนดใหม่(1);

list[0].next =new Node(4);

list[0].next.next =โหนดใหม่(5);

รายการ[1] =โหนดใหม่(2);

list[1].next =โหนดใหม่(3)

list[1].next.next =โหนดใหม่(6)

list[1].next.next.next =โหนดใหม่(8);

ผลผลิต − รายการที่รวมกันคือ -->

1>> 2>> 3>> 4>> 5>> 6>> 8>> ว่าง

คำอธิบาย −เราได้รับรายชื่อเชื่อมโยงจำนวน K ซึ่งจัดเรียงตามลำดับ กระบวนการรวมประกอบด้วยการเปรียบเทียบส่วนหัวของรายการที่เชื่อมโยงโดยใช้ฟังก์ชันตัวเปรียบเทียบจาวาและรวมเข้าด้วยกันในอาร์เรย์ผลลัพธ์

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

• เรากำลังป้อนข้อมูลด้วยจำนวน list(K) ที่จำเป็นต้องรวม

• คลาสโหนดถูกเตรียมใช้งานซึ่งมีหน้าที่สร้างโหนดของรายการที่เชื่อมโยง

• หลังจากนั้นโหนดของรายการที่เชื่อมโยงจะเริ่มต้นในลำดับที่เรียงลำดับและส่วนหัวของรายการที่เชื่อมโยงจะถูกส่งผ่านฟังก์ชัน (mergeLists) โดยมีพารามิเตอร์เป็น k

• ภายในฟังก์ชัน วนซ้ำจากรายการที่สองเป็นต้นไป ภายในลูป วนซ้ำอีกลูปซึ่งมียูทิลิตี้ทั้งหมดสำหรับการเปรียบเทียบองค์ประกอบ

• ส่วนหัวของทั้งรายการแรกและรายการที่ i ถูกจับและจัดเก็บไว้ในตัวแปร

• จากนั้นตรวจสอบส่วนหัวทั้งสองสำหรับองค์ประกอบส่วนหัวที่เล็กกว่า จากนั้นผลลัพธ์และส่วนหัวผลลัพธ์จะถูกตั้งค่าเป็นส่วนหัวของรายการสุดท้าย

• จากนั้นจึงทำกระบวนการที่คล้ายกันสำหรับองค์ประกอบต่อไปนี้ของรายการ จากนั้นข้อมูลจะถูกเปรียบเทียบและจัดเก็บตามลำดับที่ถูกต้อง

• หากรายการถูกวนซ้ำจนถึงจุดสิ้นสุด โหนดสุดท้ายจะถูกตั้งค่าเป็น null และรายการสุดท้ายจะถูกส่งคืนไปยังผู้ใช้เป็นเอาต์พุต

ตัวอย่าง

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;
      priorityQueue = new PriorityQueue<Node>(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");
   }
}

ผลลัพธ์

หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้

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