1.

Given a linked list with each node representing a linked list and two pointers of its type given below. You need to flatten the lists into a single linked list. The flattened linked list also needs to be sorted. Discuss the approach.

Answer»
  • Pointer to the next node in the main list (the "right" pointer).
  • Pointer to a linked list, this node being the head (the 'down' pointer).

The APPROACH is to use the merge() procedure of merge sort for linked lists. To merge lists one by one, we use merge(). We merge() the current list with the flattened list recursively.
The flattened list's nodes are linked via the down pointer.

Another approach is to use heaps. It is important to notice that there are N nodes connecting in a downward manner from each top node, but those downward nodes are in sorted ORDER. As a result, the objective is to sort everything in ASCENDING order (or decreasing order).

  • Push all the heads of the linked lists in the priority queue's downward list.
  • Pop the node with the smallest priority from the priority queue.
  • Check the node's location so that the next node which is being pointed by the current node can be inserted into the priority queue.
  • Pop the smallest element once more and push the next node pointed by the current node until the heap is empty.
  • Continue to add node data to a new linked list that is POPPED out to the new list.
  • Print the above-mentioned linked list.
struct CMP { bool operator()(Node* x, Node* y) { return x->value > y->value; }};//the following function returns the flattened linked list’s rootNode* flattenList(Node* root){ Node* p = root; Node* head = NULL; // this min heap returns the current smallest element in the heap priority_queue < Node*, vector <Node*>, cmp > pqueue; // the head nodes of every // downward linked list is pushed into the heap while (p) { pqueue.push(p); p = p->right; } while (!pqueue.empty()) { // pop out the topmost node Node* t = pqueue.top(); pqueue.pop(); if (t->down) { pqueue.push(t->down); } // Create the required linked list if (head != NULL) p->down = t; else head = t; p = t; p->right = NULL; } // Pointer to head node return head;}void printList(Node* head){ while (head != NULL) { cout << head->value << ” “ << endl; head = head->down; }}

Time Complexity : O(nlogn)
Space Complexity : O(n)

Conclusion:

We hope that this article has helped you learn the fundamentals and advanced questions of linked lists. These questions cover the most important concepts related to linked lists which will help you in both interview and understanding this data structure in depth.


Discussion

No Comment Found

Related InterviewSolutions