Sort A “K” Sorted Doubly Linked List
You’re given a doubly-linked list with N nodes, where each node deviates at max K position from its position in the sorted list. Your task is to sort this given doubly linked list.

For example :

Let us consider K is 3, an element at position 4 in the sorted doubly linked list, can be at positions 1, 2, 3, 4, 5, 6, 7 in the given linked list because the absolute difference of all these indices with 4 is at most 3.

Note :

All elements are distinct. A doubly linked list is a type of linked list that is bidirectional, that is, it can be traversed in both directions, forward and backward.

Input Format :

The first line of input contains T, the number of test cases. The first line of each test case contains an integer K, as specified in the problem statement. The second line contains the elements of the doubly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output Format :

For each test case print in a new line the sorted linked list, the elements of the sorted list should be single-space separated, terminated by -1.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Sort A “K” Sorted Doubly Linked List

You’re given a doubly-linked list with N nodes, where each node deviates at max K position from its position in the sorted list. Your task is to sort this given doubly linked list.

For example :

Let us consider K is 3, an element at position 4 in the sorted doubly linked list, can be at positions 1, 2, 3, 4, 5, 6, 7 in the given linked list because the absolute difference of all these indices with 4 is at most 3.

Note :

All elements are distinct.

A doubly linked list is a type of linked list that is bidirectional, that is, it can be traversed in both directions, forward and backward.

Input Format :

The first line of input contains T, the number of test cases.

The first line of each test case contains an integer K, as specified in the problem statement.

The second line contains the elements of the doubly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

Output Format :

For each test case print in a new line the sorted linked list, the elements of the sorted list should be single-space separated, terminated by -1.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10000
1 <= K < N

Time Limit: 1 sec

Accepted Answer

Sort the given doubly linked list using the insertion sort technique. While inserting each element in the sorted part of the list, there will be at most k swaps to place the element to its correct position since it is at most k steps away from its correct position.

Accepted Answer

Insertion Sort Approach

We will use Insertion sort to sort the doubly linked list efficiently.

Iterate the given doubly linked list head till the last node n, where n is the size of the doubly linked list.

Compare the current element (key) to its predecessor.
If the key element is smaller than its predecessor, compare elements before. Move the greater elements one position up to make space for the swapped element.

Let’s understand this in a detailed way.

Start by making a Node *current = head and then run a loop till current is not NULL.
Make a Node *back = current -> prev and an integer variable named key = current->data.
Now run a loop till back is not NULL and the key is less than current->data.
Inside this loop update back -> next -> data = back -> data and back= back -> prev.
After exiting this loop check if the back is NULL or not. If it is NULL, then update head -> data = key;
Else update back -> next -> data = key, and after this update current = current -> next.
At last return head, which is our answer.

Space Complexity: O(1)Explanation:

O(1)

As we are using constant extra memory.

Time Complexity: OtherExplanation:

O(N * K), where N is the number of elements in the doubly linked list and K is the maximum deviation of an element from its target position.

In the worst case, to move every element to its correct place, at most K elements need to be moved.

Java (SE 1.8)

/*

    Time Complexity: O(N * K)

    Space Complexity: O(1),



    where N is the number of elements in the doubly linked list and K is the maximum deviation of an element from its target position.

*/



public class Solution {



    public static Node sortedDll(Node head, int k) {

        

        // Assign the head of the Linked List to current.

        Node current = head;

        

        // Traverse till you you reach the end of the list.

        while (current != null) {

            Node back = current.prev;

            int key = current.data;

        

            // Swapping if value of back->data is greater than key value.

            while (back != null && key < back.data) {

                back.next.data = back.data;

                back = back.prev;

            }



            // If back pointer points to NULL, update data of head as given.

            if (back == null) {

                head.data = key;

            }



            else {

                back.next.data = key;

            }



            // Updating the value of current as given.

            current = current.next;

        }



        return head;

    }



}

Python (3.5)

'''
	Time Complexity: O(N * K)
	Space Complexity: O(1),

	where N is the number of elements in the doubly linked list and K is the maximum deviation of an element from its target position.
'''

def sortedDll(head, k):

	# Assign the head of the Linked List to current.
	current = head
	
	# Traverse till you you reach the end of the list.
	while (current != None):
	
		back = current.prev
		key = current.data
		
		# Swapping if value of back.data is greater than key value.
		while (back != None and key < back.data):
		
			back.next.data = back.data
			back = back.prev
		
		# If back pointer points to None, update data of head as given.
		if (back == None):
			head.data = key
		else:
			back.next.data = key
		

		# Updating the value of current as given.
		current = current.next
	
	return head

C++ (g++ 5.4)

/*

    Time Complexity: O(N * K)

    Space Complexity: O(1),



    where N is the number of elements in the doubly linked list and K is the maximum deviation of an element from its target position.

*/



Node *sortedDll(Node *head, int k) {



    // Assign the head of the Linked List to current.

    Node *current = head;



    // Traverse till you you reach the end of the list.

    while (current != NULL) {

        Node *back = current->prev;

        int key = current->data;



        // Swapping if value of back->data is greater than key value.

        while (back != NULL && key < back->data) {

            back->next->data = back->data;

            back = back->prev;

        }



        // If back pointer points to NULL, update data of head as given.

        if (back == NULL) {

            head->data = key;

        }



        else {

            back->next->data = key;

        }



        // Updating the value of current as given.

        current = current->next;

    }



    return head;

}

Accepted Answer

Min Heap Approach

We will start by creating a Min Heap(or a priority queue) of size k+1 with the data of the first k+1 nodes. Also make two pointers named next and prev, where prev points to the previous node and next point to the next node.
We will maintain a priority queue giving priority to the minimum element(min-heap) and we’ll then insert the data of the first k+1 nodes in the queue.
We will run a loop from k+1 till N(Number of nodes in the doubly linked list). We will then start assigning the top element of the queue to the data of the first node of the doubly linked list(we’ll initialize a variable index=0) and then pop this value and also increment the index.
At the same time, we will push the value at which the next pointer is pointing in the loop(it can be from K+1 to N).
After this loop terminates, i.e all the elements from the doubly linked list have been added to the queue. Then, we will just assign the top element of the queue to the linked list and pop that value. We will do this till the queue is empty.
Finally, we will print the K sorted doubly linked list.

Let us understand the working of the above algorithm with the help of an example, where N(Number of nodes in the doubly linked list) = 4, K = 2, and the doubly linked list is:

NULL←5←→6←→2←→3→NULL

We will create a priority queue of size 3(K + 1) and insert the first 3 values {5, 6, 2} in it and also create an integer variable index which is initialized to be 0.
Then we will run a for loop from 3(K + 1) to 4(N) and start assigning the linked list(from the start of the linked list using index variable which was initialized to be 0), to have the value of the top of the queue which will return the value of the smallest value from the queue which will be 2. Hence our first element in the answer linked list is 2, now we will pop this out of the queue and push a new element in the linked list which will be 3.
Now in our case, our loop is terminated as N = 4(Number of nodes in the doubly linked list) has been achieved, so we need not push more elements in the list.
We’ll keep assigning the top element of the queue to our final list, and pop the top element till the queue becomes empty, and finally print the final linked list.
After we pushed 3 in our queue, our 2nd element of our final linked list which is nothing but the top of the queue will be added to the final linked list and our new linked list will look like {2, 3}.
Similarly, we’ll add 5 and 6 to our final linked list and pop them from the queue, and finally now as the queue is empty we’ll just print our final linked list which is {2, 3, 5, 6}.

Space Complexity: OtherExplanation:

O(K), where K is the maximum deviation of an element from its target position.

This is the size of the Min heap(or a priority queue).

Time Complexity: OtherExplanation:

O(N * LogK), where N is the number of nodes in the given linked list and K is the maximum deviation of an element from its target position.

As removing an element and adding a new element to min heap will take logK time, hence for N nodes it will be O( N * log K)

C++ (g++ 5.4)

/*

    Time Complexity: O(N * LogK)

    Space Complexity: O(K),



    where N is the number of elements in the doubly linked list and K is the maximum deviation of an element from its target position.

*/



// Comparator class to compare two nodes.

class comp {

public:

    bool operator()(Node *a, Node *b)

    {

        if (a == NULL) {

            return false;

        }



        if (b == NULL) {

            return true;

        }



        return (a->data > b->data);

    }



};



Node *sortedDll(Node *head, int k) {

    // Min-Heap(Priority queue) for storing data of nodes

    priority_queue, comp> q;



    int count = 0;



    // Traverse till you reach the end of the list and count is less than or equal to K.

    while (head != NULL && count <= k) {

        q.push(head);

        count++;

        head = head->next;

    }



    Node *sortedList = NULL;



    Node *prevNode = NULL;

    

    // Travserse till queue is non-empty.

    while (q.size() > 0) {

        Node *top = q.top();

        q.pop();

    

        // If head is not NULL then push the current head into thr queue and update head as given.

        if (head != NULL) {

            q.push(head);

            head = head->next;

        }



        // If sortedList points to NULL, then assign the top value of the queue to sortedList and make it's previous value as NULL.

        if (sortedList == NULL) {

            sortedList = top;

            sortedList->prev = NULL;

            prevNode = sortedList;

        }



        else {

            top->prev = prevNode;

            prevNode->next = top;

            prevNode = top;

        }



    }



    // Updating next pointer of prevNode as NULL.

    prevNode->next = NULL;



    return sortedList;

}

Java (SE 1.8)

/*

    Time Complexity: O(N * LogK)

    Space Complexity: O(K),



    where N is the number of elements in the doubly linked list and K is the maximum deviation of an element from its target position.

*/

    

import java.util.PriorityQueue;

import java.util.Comparator;



// Comparator class to compare two nodes.

public class Solution {



    static class compareNode implements Comparator> {



        @Override

        public int compare(Node a, Node b) {

            if (a == null) {

                return 0;

            }



            if (b == null) {

                return 1;

            }



            return (a.data - b.data);

        }



    }



    public static Node sortedDll(Node head, int k) {

        // Min-Heap(Priority queue) for storing data of nodes

        PriorityQueue< Node > q = new PriorityQueue< Node >(new compareNode());



        int count = 0;

        

        // Traverse till you reach the end of the list and count is less than or equal to K.

        while (head != null && count <= k) {

            q.add(head);

            count++;

            head = head.next;

        }



        Node sortedList = null;



        Node prevNode = null;

       

        // Travserse till queue is non-empty.

        while (q.size() > 0) {

            Node top = q.poll();

           

            // If head is not NULL then push the current head into thr queue and update head as given.

            if (head != null) {

                q.add(head);

                head = head.next;

            }



            // If sortedList points to NULL, then assign the top value of the queue to sortedList and make it's previous value as NULL.

            if (sortedList == null) {

                sortedList = top;

                sortedList.prev = null;

                prevNode = sortedList;

            }



            else {

                top.prev = prevNode;

                prevNode.next = top;

                prevNode = top;

            }

        }



        // Updating next pointer of prevNode as NULL.

        prevNode.next = null;



        return sortedList;

    }



}

Python (3.5)

'''
	Time Complexity: O(N * LogK)
	Space Complexity: O(K),

	where N is the number of elements in the doubly linked list and K is the maximum deviation of an element from its target position.
'''

class Node:
	def __init__(self, data):
		self.data = data
		self.next = None
		self.prev = None
	
	def __del__(self):
		if(self.next):
			del self.next

import heapq

def sortedDll(head, k):

	setattr(type(head), "__lt__", lambda self, other: self.data <= other.data)

	# Min-Heap(Priority queue): for storing data of nodes
	q = []

	count = 0
	# Traverse till you reach the end of the list and count is less than or equal to K.
	while (head != None and count <= k):
		heapq.heappush(q, head)
		count += 1
		head = head.next

	sortedList = None

	prevNode = None
	
	# Travserse till queue is non-empty.
	while (len(q) > 0):
	
		top = heapq.heappop(q)
	
		# If head is not None then push the current head into thr queue and update head as given.
		if (head != None):
		
			heapq.heappush(q, head)
			head = head.next
		

		# If sortedList points to None, then assign the top value of the queue to sortedList and make it's previous value as None.
		if (sortedList == None):
		
			sortedList = top
			sortedList.prev = None
			prevNode = sortedList
		
		else:
		
			top.prev = prevNode
			prevNode.next = top
			prevNode = top
	

	# Updating next pointer of prevNode as None.
	prevNode.next = None

	return sortedList

You’re given a doubly-linked list with N nodes, where each node deviates at max K position from its position in the sorted list. Your task is to sort this given doubly linked list.

For example :

Note :

Input Format :

Output Format :

Note :

Constraints :

Top Nagarro SDE interview questions & answers

Popular interview questions of SDE