Does this merge function of Mergesort take O (1) space or O(n) space?

Question

private ListNode merge(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            curr.next = list1;
            list1 = list1.next;
        } else {
            curr.next = list2;
            list2 = list2.next;
        }
        curr = curr.next;
    }
    if (list1 == null) {
        curr.next = list2;
    } else {
        curr.next = list1;
    }
    return dummy.next;
}

Here I believe due to " curr" node it takes O(n) space as curr node would gradually contain complete linked list.

Answer 1

This merge function uses O(1) space. Aside from the local variables which have a constant size, it only allocates a single ListNode in ListNode dummy = new ListNode(0);

The rest of the function just changes the next members of the list elements pointed to by list1 and list2.

It is possible to modify the function to not even allocate a single extra object by writing an initial test to select the initial node of the resulting list.

Combining this function with a top down recursive approach or a bottom up iterative one yields a sorting algorithm with an O(log(N)) space complexity and a O(N.log(N)) time complexity.

To achieve stable sort, the comparison operator should be changed to <=.

Here is a modified version without any allocation:

private ListNode merge(ListNode list1, ListNode list2) {
    Listnode head, curr;
    if (list1 == null)
        return list2;
    if (list2 == null)
        return list1;
    if (list1.val <= list2.val) {
        curr = head = list1;
        list1 = list1.next;
    } else {
        curr = head = list2;
        list2 = list2.next;
    }
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            curr = curr.next = list1;
            list1 = list1.next;
        } else {
            curr = curr.next = list2;
            list2 = list2.next;
        }
    }
    curr.next = (list1 != null) ? list1 : list2;
    return head;
}

Here is a modified version with fewer tests in most cases:

private ListNode merge(ListNode list1, ListNode list2) {
    Listnode head, curr;
    if (list1 == null)
        return list2;
    if (list2 == null)
        return list1;
    if (list1.val <= list2.val) {
        curr = head = list1;
        list1 = list1.next;
        if (list1 == null) {
            curr.next = list2;
            return head;
        }
    } else {
        curr = head = list2;
        list2 = list2.next;
        if (list2 == null) {
            curr.next = list1;
            return head;
        }
    }
    for (;;) {
        if (list1.val <= list2.val) {
            curr = curr.next = list1;
            list1 = list1.next;
            if (list1 == null) {
                curr.next = list2;
                return head;
            }
        } else {
            curr = curr.next = list2;
            list2 = list2.next;
            if (list2 == null) {
                curr.next = list1;
                return head;
            }
        }
    }
}

In C or C++, the original code can be changed to avoid allocation with pointers:

static ListNode *merge(ListNode *list1, ListNode *list2) {
    ListNode *head = NULL;
    ListNode **nextp = &head;
    while (list1 && list2) {
        if (list1->val <= list2->val) {
            *nextp = list1;
            nextp = &list1->next;
            list1 = list1->next;
        } else {
            *nextp = list2;
            nextp = &list2->next;
            list2 = list2->next;
        }
    }
    *nextp = list1 ? list1 : list2;
    return head;
}