Merge k Sorted Lists

Today's challenge was about data structure. Something I haven't really paid attention to before.

The requirement was to merge sorted linked lists into one long sorted list

Thought process

Since Data structure wasn't my strength before this challenge, my first approach was to go on YouTube and learn a little about it to code the challenge.

After my research, I learnt about a way to merge sorted lists but the problem was now that the method will only merge two lists at once. So my thought now shifted to how I could be merging two lists at once and returning to the array till there's one long linked list left in the array and I will then return it.

Implementation

I jumped straight to code the solution after taking some jottings from my research.

The first thing I did was to create a function that takes two arguments(the lists to be merged) that will merge two lists. Since the lists were already sorted, I didn't bother so much about sorting them individually. All I paid attention to was linking them based on their order from the different lists. For example

list a = 1 ->2 ->3
list b = 3 ->4 ->6

In this case, I set a condition that checks if the first value(head element) of list a is less than the list b first value (head element). In this case, it's true and so I will add the first value of list a first and repeat the same thing and when it's false I will add the first value of list b.

Before this check implementation, I already created a new ListNode() and it was empty initially and name it dummy.

In the merge function, I returned the dummy list(which is the new merged list).

After creating the merge function, I then went on to write the logic that will remove two lists (list a and list b) from the array and then pass the two lists into the merge function created initially as arguments. After merging, I then pushed the new single list back to the array and kept repeating the same method since I used a while loop till it's only one list left in the array and then returned the first element of that array which is the merged list.

What I learnt

I was able to learn a little bit about linked list data structure. It was the basic, but I will build on that

Conclusion

Again, I was able to learn about new concepts and I'm happy about that. All thanks to Ingressive for Good for this challenge. It's the ninth day and I'm really pleased

Thank you for reading through!

Day nine(9) done, one(1) more day to go!

You can follow me on Twitter