[INTERESTING] What's the time complexity for this problem?

This is the problem to flatten the linked lists.

I thinks the time complexity is O(n^2) , where n is no. of nodes.

If we consider average length of linked list to be k, then for merging 1st 2 list the time complexity is 2k, and for merging resultant with the next its 3k and so on
so 2k + 3k+ … + (no. of lists )

and no. of lists = n/k = m

so it would be O((m(m+1)/2)k) which would be O(m^2k) => O(n^2/k) => O(n^2).

What do you say ?