Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

You are given a linked list containing *'n'*** 'head'** nodes, where every node in the linked list contains two pointers:

(1) ** ‘next’** which points to the next node in the list

(2) ** ‘child’** pointer to a linked list where the current node is the head.

Each of these child linked lists is in sorted order and connected by 'child' pointer.

Your task is to flatten this linked such that all nodes appear in a single layer or level in a *'sorted order'**.*

```
Input: Given linked list is:
```

```
Output:
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 12 → 20 → null.
Explanation:
The returned linked list should be in a sorted order. All the elements in this returned linked list are connected by 'child' pointers and 'next' pointers point to null.
```

Detailed explanation

```
The first line of the input contains a single integer ‘n’ which represents the number of head nodes in the linked list.
The next '2n' lines represent 'n' linked lists connected by next pointer at the head. Description of each of these linked lists is as follows:
The first line contains a single integer 'k', number of nodes in the current linked list.
The next line contains 'k' spaced integers, representing elements of the linked list.
```

```
Return the head node of the final linked list.
```

```
You don’t have to print anything, it has already been taken care of. Just implement the given function. The flattened list will be printed using the child pointer.
```

```
4
3
1 2 3
3
8 10 15
2
18 22
1
29
```

```
1 2 3 8 10 15 18 22 29
```

```
The given linked list is
```

```
Therefore after flattening the list will become-
1 -> 2 -> 3 -> 8 -> 10 -> 15 -> 18 -> 22 -> 29 ->null
```

```
5
2
4 6
2
5 71
3
7 8 9
3
11 12 19
3
14 15 17
```

```
4 5 6 7 8 9 11 12 14 15 17 19 71
```

```
Try solving this in O(n*n*k), where ‘n’ denotes the number of head nodes and ‘k’ is the average number of child nodes in all 'n' sub-lists.
```

```
Try solving this without using any extra space.
```

```
1 <= n <= 100
1 <= k <= 20
1 <= Node.data <= 10^9
Time Limit: 1 sec
```