Merging k Sorted Lists in C++

Overview

Linked List is by far one of the most popular and useful data structures being used in software engineering. This DS has lots of applications for day-to-day needs. S linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next.

In this task, we will be merging a number of the sorted list, the lists to be merged into one are already sorted therefore reducing the workload of only combining the lists into one.

Thought Process

If we visualize the task as having an input of this nature [[1, 3, 4], [2, 2, 3], [1, 4, 6, 7], [7, 8, 9]], the approach that can be used here is to first merge all the array into one, we can traverse all the lists in the input and put every element of all the array into a single array.

for(int i=0;i<lists.size();i++)
.
.
.
newArray.push_back(temp->val);

After having a single array containing all our list elements, we can then perform a sorting algorithm on the new array so they can be sorted.

sort(newArray.begin(),newArray.end());

With this, we can then create a new sorted linked list and add new nodes.

Conclusion

Linked list as stated earlier is a very important data structure that is always handy for developers. In this task, skills in working with linked lists and also sorting algorithms are tested.