educative.io

Educative

How is space complexity linear?

Merge Two Sorted Linked Lists

Given two sorted linked lists, merge them so that the resulting linked list is also sorted.

How’s the space complexity O(M+N) here?
It should O(1) right? Since we are just merging two LinkedList, we are using constant number of pointers and readjusting the LL order in place, since it’s LL. So no additional space.

Hi Vaishnavi!

The space complexity is O(m+n) here because we are creating a new linked list that contains all the nodes of the initial two linked lists, rather than inserting the elements of one list into another.

@Vaishnavi, in the worst case when both lists are equal in length, you need to move into the merged list all nodes. Thus, you get O(M+N), where M and N are the lengths of the two lists.

Edit: to clarify, the merged list needs to be sorted too. You don’t just append one list to the end of the other. And even if that would be the case, you’d still need to find the end of one of the lists, hence, it wouldn’t be O(1).