23. Sort a 'k' sorted doubly linked list

23. Sort a 'k' sorted doubly linked list

Problem link :- click here

package Linked_List;

import java.util.PriorityQueue;

public class LinkedList__23
{

	static void sortDLL(DoublyLinkedList list, int k)
	{
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		//step 1 :-
		//adding first k nodes to the priority queue
		Node2 node = list.head;
		for(int i=0; i<k+1; i++)
		{
			pq.add(node.data);
			node = node.next;
		}
		
		//step 2 :-
		//sliding window technique
		int n = list.size();
		Node2 temp = list.head;
		for(int i=k+1; i<n; i++)
		{
			//peek of the pq is placed in the first node of the window
			temp.data = pq.poll();
			
			//removing the first node of the window and
			//adding one more node to the pq
			pq.add(node.data);
			node = node.next;            //from first step
			
			//updating temp
			temp = temp.next;
		}
		
		//step 3 :-
		//last k nodes will be in the pq we have to place that value to the temp
		while( !pq.isEmpty() )
		{
			temp.data = pq.poll();
			
			temp = temp.next;
		}
	}
	
	
	//Time complexity for this approach is   O(n * k)
	//Here we will traverse from the first node 
	//and fill the node(one we are pointing to)
	//since we are in the first node        we should place the minimum value node 
	//and we know     that node is present in next    k     nodes 
	//and this goes on as our previous part is already sorted 
	static void sort(DoublyLinkedList list, int k)
	{
		if(list.head == null  ||   list.head.next == null)
			return;
		
		Node2 cur = list.head;
		
		while(cur != null)
		{
			Node2 min = null;
			Node2 temp = cur.next;
			for(int i=0; (i<k &&  temp!=null); i++)
			{
				if(temp.data < cur.data)
					min = temp;
				temp = temp.next;
			}
			
			if(min != null)
			{
				int x = cur.data;
				cur.data = min.data;
				min.data = x;
			}
			
			cur = cur.next;
		}
	}
	
	public static void main(String[] args)
	{
		DoublyLinkedList list = new DoublyLinkedList();
		list.push(3);
		list.push(6);
		list.push(2);
		list.push(12);
		list.push(56);
		list.push(8);
		
		int k = 2;
		
		System.out.println("Linked list before sorting : ");
		list.print();
		
		sort(list, k);
		System.out.println("Linked list after sorting : ");
		list.print();
	}

}

Time complexity :- O(n*log(k))
Space complexity :- O(k)