Lecture 143:- Flatten Linked List

Flattening a linked list involves transforming a multilevel linked list (linked list with nested linked lists) into a single-level linked list while maintaining the original order of elements. Each node in the flattened linked list will contain the data from the original nodes of the multilevel linked list.

Here's how you can flatten a multilevel linked list:

1. Traverse the main linked list.
2. If a node has a child linked list, recursively flatten the child.
3. Attach the flattened child list to the current node's next.
4. Move to the next node and continue the process.

Here's a C++ implementation of flattening a multilevel linked list:

cppCopy code

#include <iostream> class Node { public: int data; Node* next; Node* child; Node(int value) : data(value), next(nullptr), child(nullptr) {} }; Node* flatten(Node* head) { if (!head) return nullptr; Node* current = head; while (current) { if (current->child) { Node* next = current->next; current->next = current->child; current->child = nullptr; Node* last = current->next; while (last->next) { last = last->next; } last->next = next; } current = current->next; } return head; } void displayList(Node* head) { while (head) { std::cout << head->data << " "; head = head->next; } std::cout << std::endl; } int main() { Node* head = new Node(1); head->next = new Node(2); head->next->next = new Node(3); head->next->child = new Node(7); head->next->child->next = new Node(8); head->next->child->next->next = new Node(9); head->next->child->child = new Node(12); head->next->child->child->next = new Node(13); std::cout << "Original Multilevel List:" << std::endl; displayList(head); head = flatten(head); std::cout << "Flattened List:" << std::endl; displayList(head); return 0; }

In this example, the flatten function flattens the multilevel linked list. The displayList function is used to display the original and flattened lists.

The time complexity of flattening a multilevel linked list is O(n), where n is the total number of nodes in the list.