Java에서 K 정렬 연결 목록 병합

<시간/>

순서대로 정렬된 다양한 크기의 연결 목록이 K개 주어지고 결과 배열이 순서대로 정렬되지 않고 결과 배열이 출력으로 인쇄되는 방식으로 목록을 결과 목록으로 병합해야 합니다. 사용자입니다.

예를 들어 이해합시다:-

입력 -

정수 k =3;

목록[0] =새로운 노드(11);

list[0].next =새로운 노드(15);

list[0].next.next =새로운 노드(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개의 연결 리스트가 주어진다. 병합 과정에는 자바 비교기 기능을 사용하여 연결 목록의 헤드를 비교하고 결과 배열에서 함께 병합하는 과정이 포함됩니다.

입력 -

정수 k =2;

목록[0] =새 노드(1);

list[0].next =새로운 노드(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>> null

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다 -

병합이 필요한 목록(K)의 개수를 입력 받습니다.
연결 리스트의 노드 생성을 담당하는 노드 클래스가 초기화됩니다.
그 후 연결 리스트의 노드는 정렬된 순서로 초기화되고 연결 리스트의 헤드는 매개변수가 k
인 함수(mergeLists)를 통해 전달됩니다.
함수 내에서 루프는 두 번째 목록부터 루프 내에서 반복되며 요소 비교를 위한 모든 유틸리티를 포함하는 다른 루프가 반복됩니다.
첫 번째 목록과 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