FOR FREE MATERIALS

Flattening a linked list is performed on a linked list that’s every node points to another linked list. For that, each node of the linked list has two pointers. One is to point to the next node of the main list and another pointer which is storing the address of another node. 

Each node has three parts -

# Data Part

# The Address Part Pointing To The Next Node

# The Address Part Pointing To Another List

The structure of each node:

Suppose the given list to flatten is:

First, a pointer ’ptr’ will point to the first node of the list.

First, the data of the ‘ptr’ will be inserted into another list which will store the flattened list.

Now, another pointer ‘ptr1’ will be taken which will point to the list pointed by ‘ptr’.

Now, the data of ‘ptr1’ will be inserted into the list. Hence, the list will be:

Then ‘ptr1’ will be moved to the next node and the data will be inserted into a flattened list till ‘ptr1’ not becomes ‘null’. When the ‘ptr1’ will be null the flattened list will be:

After that, the pointer ‘ptr’ will be moved to the next node of the main list and the data will be inserted into the flattened list.

The aforesaid process will be repeated again.

After, copying all the elements in the flattened list we get:

Now the second step is to sort the list by using any sorting technique. After sorting the list we will get the final flattened list as:

INPUT: 

The number of elements to create the list and the elements which are to be inserted.

OUTPUT: 

a) The lists after creating them.

b) The flattened list. 

PROCESS:

Step 1: 

Define a structure named ‘node’ which has three parts−

The data part of integer type. 

The ‘next’ (points to its next node i.e. the address of the next node) part is a structure (node) type pointer.

The ‘child’ points to another list.

Step 2: Create a function “node* createlist()”

Step 2.1: Take the number of elements from user in an ‘integer’ type variable ‘n’

Step 2.2: for i = 0 to (n - 1) repeat Step 2.3 to Step 2.7

Step 2.3: Take the element which is to be inserted in an integer type variable ‘x’.

Step 2.4: Create a new node in ‘p’(a ‘node’ type pointer) by using ‘malloc’ function.                   

                Set data[p] ⇒ x

                Set next[p] ⇒ Null 

                Set child[p] = NULL

Step 2.5: If (head1 = Null) then

                    Set head1 ⇒ p

               [End of ‘If’ ]

Step 2.6: Else   

                   Set next[ptr] ⇒ p

              [End of ‘Else’] 

Step 2.7: Set ptr ⇒ p

               [End of Step 2.2 ‘For’ loop]

Step 2.8: Return ‘head1’

               [End of the function “node* createlist( )”] 

Step 3: Create a function “void displaylist(node * head)”

Step 3.1: Set p ⇒ head

Step 3.2: While(p ≠ Null) then repeat  Step 3.3 and Step 3.4

Step 3.3:     Print data[p]

Step 3.4:     Set p ⇒ next[p]             

              [End of Step 3.2 ‘While’ loop]

[End of the function “void displaylist(node *head)”]

Step 4: Create a function “void swap(node *a,node *b)” 

Step 4.1:       Set tmp ← data[a] 

Step 4.2:       Set data[a] ← data[b]

Step 4.3:       Set data[b] ← tmp 

            [End of the function ‘void swap(node *a, node *b)’]

Step 5: Create a function “void sort(node *head)” 

Step 5.1:       if head = NULL then return

                     [End of step 5.1 ‘if’] 

Step 5.2: Repeat from step 5.3 to step 5.8 While flag=1

Step 5.3:            Set flag ← 0 

Step 5.4:           Set ptr ← head 

Step 5.5:           while next[ptr] ≠ ptr1 repeat step 5.6 to step 5.7

Step 5.6:                    if data[ptr] > data[next[ptr]] then 

                                           swap(ptr,next[ptr])

                                           Set flag ← 1 

                                 [End of step 5.6 ‘if’] 

Step 5.7:                  Set ptr ← next[ptr] 

                        [End of step 5.5 ‘while’ loop] 

Step 5.8:        Set ptr1 ← ptr 

               [End of step 5.2 ‘while’ loop]

[End of function ‘void sort(node *head)’]

Step 6: Create a function “void flattening(node *head)” 

Step 6.1:       Set ptr ← head

Step 6.2:       while ptr ≠ NULL repeat step 6.3 to step 6.12

Step 6.3:                     Create a node pointed by a pointer ‘p’

                                    Set data[p] ← data[ptr]

                                    Set next[p] ← child[p] ← NULL

Step 6.4:                     if headf = NULL then

                                                       Set headf ← p

                                   else

                                                      Set next[ptrf] ← p

                                  [End of step 6.4 ‘if’]

Step 6.5:                                       Set ptrf ← p

Step 6.6:                                       Set ptr1 ← child[ptr]

Step 6.7:                  while ptr1≠NULL then repeat step 6.8 to step 6.11

Step 6.8:                                     Create a new node pointed by a pointer ‘p’

                                                    Set data[p] ← data[ptr1]

                                                    Set next[p] ← child[p] ← NULL

Step 6.9:                                     if headf = NULL then

                                                                       Set headf ← p

                                                   else

                                                                       Set next[ptrf] ← p

                                                  [End of step 6.9 ‘if’]

Step 6.10:                                                     Set ptrf ← p

Step 6.11:                                                     Set ptr1 ← next[ptr1]

                              [End of step 6.7 ‘while’ loop]

Step 6.12:                               Set ptr ← next[ptr]

                     [End of step 6.2 ‘while’ loop]

Step 6.13: Print "The list after flattening: "

Step 6.14: Call the function ‘sort(headf)’

Step 6.15: Call the function ‘displaylist(headf)’

[End of function ‘void flattening(node *head)’]

Step 7: Create a function “int main()” 

                    Step 7.1: Set head ← createlist()

                    Step 7.2: print "The main list is: "

                    Step 7.3: Call the function ‘displaylist(head)’

                    Step 7.4: Set ptr ← head

                    Step 7.5: Set I ← 1

                    Step 7.6: while ptr ≠ NULL repeat step 7.7 to step 7.9

                                    Step 7.7: Set child[ptr] ← createlist()

                                    Step 7.8: Set ptr ← next[ptr]

                                    Step 7.9: Set i ← i + 1

                    [End of step 7.6 ‘while’ loop]

                    Step 7.10: Set ptr ← head

                    Step 7.11: Set i ← 1

                    Step 7.12: while ptr ≠ NULL repeat 7.13 to step 7.15

                                                             Step 7.13: call the function ‘displaylist(child[ptr])’

                                                             Step 7.14: Set ptr ← next[ptr]

                                                             Step 7.15: Set i ← i + 1 

                    [End of step 7.12 ‘while’ loop]

                    Step 7.16: call the function ‘flattening(head)’ 

[End of function ‘int main()’]