2/7/2021
Doing this for CSci 4041, after we've learned MergeSort.
What I have for now:
While it works, the runtime is 99ms. I'm expecting it's because I've used mergeTwoLists(which was made in 21.) n times, while each call cause a runtime of O(n), thus the total is O(n^2).
I think It can get better if I use the "divide and conquear" algs as we discussed in class, I would expect a runtime of O(nlogn) if everything is correct.
Also, the mergeTwoLists function can be changed as well, as I've described in the txt file created, "instead of using output, we can just add new nodes inside l1". I'll find a time to deal with that.
So I've tried to do it recursively, and it gets really messy, as I need another helper function splitArrayInToTwo() to help me split it, and while I'm doing that the run time is O(n), because java's array cannot simply use ":" to divide, I would have to copy each node one by one.
I think I'm gonna check on the answers,
OK, seems that my previous solution is actually O(kN), where k is the number of total linked lists, I guess that makes sense, but I got the idea, and I'm gonna try writing div&con method again, which ideally would have a time complexity of O(n) (简书的公式系统做的真棒啊，好评).
嘻嘻嘻嘻嘻嘻
So running it recursively did improve the runtime A LOT. I'm gonna just let go of the problem left with mergeTwoLists, since it wouldn't affect the runtime but just created more space in the memory.
Oh almost forgot, here's my final solution, I'm actually pretty proud of solving this recursively, probably needs to thank OCaml for that :).
Until next time;;
