Flattening a Linked List: Guide

ByIshita Juneja
monitor-ga803d3ec4_640-361f5b53

There are a lot of programmers who are finding it hard to solve the Flatten a Linked List problem. It is because they don’t have a proper concept of the problem and the approach that is required to solve it. 

The problem can be easily solved if you are aware of the sorting algorithms. You only need to know the right approach.  

If you are someone who is looking for a guide that can help you in solving the problem, then stick with us till the end to get better detailing on it: 

 

What does Flattening a Linked List means?

The Flattening a Linked List problem means we have to merge the different linked lists which have different head nodes. In this problem, we will be given different head nodes which will be containing some nodes with data items and addresses.

 For that given head node, we have to make a new linked list by flattening it in a way that it is in the sorted order. You might be still confused about it, thus, check the below examples to know about it in depth. 

 

Example 1

For the given linked list, flatten it.

5    – 20 – 22 – 35

|   |   |   |

8 10 19 28

| |   |

7 50 45

| |

30 40

If you see the problem, then it has 4 head nodes. The length of the list is 4, 2, 3, and 4. 

 

Solution: The Flattened List will look like this: [5, 7, 8, 10, 19, 20, 22, 28, 30, 35, 40, 45, 50].

Explanation: For the given linked list, we have to traverse it and make another list where we will sort it. After sorting all the elements into the dummy list, we will copy it to the original list. By doing this, we will be able to get the flatten linked list. 

We hope that you have got to know what we have to do with the problem. Now, let’s check another example to understand more about it. 

 

Example 2

For the given linked list, flatten it.

1    – 30 – 21 – 25

|   |   |   |

3 10 12 28

| |   |

2 15 35

| |

4 50

 

Solution: The Flatten Linked List will look like this: [1, 2, 3, 4, 10, 12, 15, 21, 25, 28, 30, 35, 50].

Explanation: For the given list, we started to iterate over the linked list to flatten it. We have to flatten it in a way that it has the head node and sorted elements. For doing this, we have to check for each element whether it is large or not. 

 

Once we have got the sorted linked list, then we will stop the iteration. However, we will use another dummy linked list for storing the value of the sorted element. Once we have got all the elements, then we will stop the iteration and copy the value of the dummy linked list to the original linked list. 

This is the information that you need to know about the problem. Now, let’s take a look at the approach that is required to solve it. We will also do a dry run for you by which you will be able to understand the problem. 

 

Flattening a Linked List 

We have already explained the Flattening a Linked List problem. Now, we have to understand the approach to solving it. It is important that you understand it properly because the iteration that we will make in the problem will be much similar to the print shortest common supersequence. 

If you don’t know, the shortest common supersequence problem is based on finding the new string by merging two strings. It is done so that we can get both strings with the help of one string. Therefore, understand the approach of Flattening a Linked List properly which is given below.

 

Problem Statement 

For the given linked list, flatten it.

5    – 10 – 19 – 28

|   |   |   |

7 20 22 35

| |   |

8 50 40

| |

10 45

 

Approach

  • First of all, we will create a dummy node to store the sorted linked list. 
  • After it, we will start the recursive calls for it. We will do it by storing the elements on the dummy node. 
  • When we are storing the value, then we will check for the elements in the dummy node by comparing the two lists at the time. We will compare the elements by “a” and “b”. 
  • When we will start our iteration, then we will initialize both a and b at the head node. 
  • After that, we will check for both numbers. If the number is smaller, then we will store it, otherwise, we will increase the a or b for the next element whichever is the largest. 
  • We will keep it going till the node reaches the null value. 
  • After reaching the null value, then we will start comparing the other node value. 
  • After doing this, we will check for the dummy linked list and will copy its value to the original linked list. 
  • Once we are done with it, then we will stop the recursive calls. 
  • Now, we will print the dummy linked list.

Now, let’s check the dry run for the approach. 

 

Dry Run

  • We will start our iteration as well as initialize the dummy list for flattening a linked list. 
  • Now, we will take two lists. Before that, we will initialize the list name for our convenience. We have assigned l1, l2, l3, and l4 in the same order, the linked lists are written. 
  • The algorithm will start merging the list l3 and l4. 
  • Now, on comparing, l3 has 19 as the first node and l4 has 28. Thus, we will assign the values a and b to both of them. 
  • For the 19 and 28, the comparison will be done. After it, the element will be stored in the dummy node. Now, after it, the a will be moved ahead to the next element which is 22. It will be compared with the 28. After the comparison, the element will be stored. 
  • We will be doing it till the a and b reach the null value. 
  • After its completion, we will move to the next list. Once the comparison is done, then we will print the sorted linked list. 

 

Wrapping Up

Flattening a Linked List is not a hard problem if you have understood the problem statement properly. Stick with the right approach, if you want to code the problem efficiently.