合并两个排序的链表：space 复杂度

Question

我正在查看 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.   

下面的答案是GFG的答案。我不明白它的 space 复杂度是 O(1)。我们正在创建一个新节点，所以它必须是 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;     
}

有人可以解释一下 space 的复杂度是 O(1) 吗？

Answer 1

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).

创建一个节点为什么要O(m+n)？该节点的大小是一个常数，因此一个节点代表 O(1) space 复杂度。创建一个节点与任一输入列表的大小无关。请注意，该节点是在循环外创建的。

实际上这样做是为了保持代码简单，但即使没有那个 dummy 节点也可以完成合并。

合并两个排序的链表：space 复杂度

Merge two sorted linked lists: space complexity

linked-list

Example 1