Merge two sorted linked lists: space complexity

Question

I am looking at the following Geeks for Geeks problem:

Given two sorted linked lists consisting of N and M nodes respectively. The task is to merge both of the list (in-place) and return head of the merged list.

Example 1
Input:
N = 4, M = 3  
valueN[] = {5,10,15,40}  
valueM[] = {2,3,20}  
Output: 2 3 5 10 15 20 40   
Explanation: After merging the two linked
lists, we have merged list as 2, 3, 5,
10, 15, 20, 40.   

Below answer is the GFG answer. I don't understand how its space complexity is O(1). We are creating a new node, so it must be O(m+n).

Node* sortedMerge(Node* head1, Node* head2)  
{  
    struct Node *dummy = new Node(0);  
    struct Node *tail = dummy;  
    while (1) {  
        if (head1 == NULL) {  
            tail->next = head2;  
            break;  
        }  
        else if (head2 == NULL) {  
            tail->next = head1;  
            break;  
        }
        if (head1->data <= head2->data){
            tail->next = head1;
            head1 = head1->next;
        }
        else{
            tail->next = head2;
            head2 = head2->next;
        }
        tail = tail->next;
    }
    return dummy->next;     
}

Could someone explain how the space complexity is O(1) here?

trincot · Accepted Answer · 2021-10-11 15:40:23Z

0

I can't understand how it's space complexity is O(1). Since we are creating a new node so it must be O(m+n).

Why should it be O(m+n) when it creates one node? The size of that node is a constant, so one node represents O(1) space complexity. Creating one node has nothing to do with the size of either of the input lists. Note that the node is created outside of the loop.

It is actually done this way to keep the code simple, but the merge could be done even without that dummy node.

answered Oct 11, 2021 at 15:40

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Mudit Kumar Over a year ago

Oh , I got it. Thanks a lot.

rcgldr Over a year ago

In C or C++, a pointer to pointer to node could be used instead of a dummy node, without needing conditional code (if statement) to handle the first node, but for languages like Java, a dummy node is commonly used. The question doesn't specify a language.

Collectives™ on Stack Overflow

Merge two sorted linked lists: space complexity

Example 1

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Example 1

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related