-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path36. FlattenLL.cpp
64 lines (53 loc) · 1.22 KB
/
36. FlattenLL.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
Time Complexity: O(n * n * k)
Space complexity: O(n * k)
Where 'n' denotes the size of the linked list and 'k' is the average number of child nodes for each of the n nodes.
*/
/*
* Definition for linked list.
* class Node {
* public:
* int data;
* Node *next;
* Node *child;
* Node() : data(0), next(nullptr), child(nullptr){};
* Node(int x) : data(x), next(nullptr), child(nullptr) {}
* Node(int x, Node *next, Node *child) : data(x), next(next), child(child) {}
* };
*/
Node *merge(Node *first, Node *second)
{
if (first == NULL)
{
second->next = nullptr;
return second;
}
if (second == NULL)
{
first->next = nullptr;
return first;
}
Node *merged = NULL;
if (first->data < second->data)
{
merged = first;
merged->child = merge(first->child, second);
}
else
{
merged = second;
merged->child = merge(first, second->child);
}
merged->next = nullptr;
return merged;
}
Node *flattenLinkedList(Node *head)
{
if (head == NULL || head->next == NULL)
{
return head;
}
head->next = flattenLinkedList(head->next);
head = merge(head, head->next);
return head;
}