Infinite Recursion error while mergesorting linked list

Question

I am applying mergesort on a linked list. Here's the problem : https://leetcode.com/problems/sort-list/

 void mergesort(ListNode* head,ListNode* low, ListNode* high){
    ListNode* slow = low;
    ListNode* fast = low;
    if (low==high) return;
    while (fast->next && fast->next->next){
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode* mid = slow;
    ListNode* mid1 = mid->next;
    mid->next == NULL;
    mergesort(head,low,mid);
    mergesort(head,mid1,high);
    merge(head,low,mid,high);
}
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode* traverse = head;
        while(traverse->next){
            traverse = traverse->next;
        }
        ListNode* high = traverse;
        cout<<high->val;
        ListNode* low = head;
        mergesort(head,low,high);
        return head;
    }
};

I commented out the merge function and the problem still persists but here's the merge code anyway:

void merge(ListNode* head, ListNode* low, ListNode* mid, ListNode* high){
    ListNode* left = low;
    ListNode* right = mid->next;
    ListNode* dummy = new ListNode(-1);
    ListNode* tp = dummy;
    while(right && left!=mid->next){
        if (left->val<right->val){
            dummy->next = left;
            dummy = left;
            left = left->next;
        }
        if (left->val>right->val){
            dummy->next = right;
            dummy = right;
            right = right->next;
        }
    }
    if (right == NULL){
        while (left!=mid->next){
            dummy->next = left;
            left = left->next;
        }
    }
    if (left == mid->next){
        while(right){
            dummy->next = right;
            right = right->next;
        }
    }
    ListNode* start1= tp->next;
    head = start1;
}

I tried to apply merge sort here the same way you would on a linear array. My dry runs say that the base case (low==high) is, infact, being reached . In the editor however, it is not reaching the base case. Its throwing some 'Deadly Signal error':

AddressSanitizer:DEADLYSIGNAL

==22==ERROR: AddressSanitizer: stack-overflow on address 0x7ffc9d343ff8 (pc 0x562648afe76b bp 0x7ffc9d344020 sp 0x7ffc9d344000 T0) ==22==ABORTING

Answer 1

The direct cause of the infinite loop is that you don't break the link between the left and right partition. You have mid->next == NULL;, but that accomplishes nothing. It should be an assignment: mid->next = NULL;

But besides that issue, there are several other problems:

• In merge you assume that right = mid->next; will assign the first node of the second list, but that is not true once you have fixed the issue above. You had just cut the two sublists, so mid->next is always going to be null. This also means a condition like left!=mid->next is no different from saying left!=nullptr. You should instead pass the head node of the second list as argument to merge, and let it be right.

• As head is a call-by-value parameter, assigning to it does not affect the caller's variable with the same name. So for example, the assignment head=start1 at the end of your code, is useless. By consequence, the caller will not know what the first node is of the sorted list. You could solve this by using a call-by-reference parameter, or return the head node reference (I will go with that latter option in the below solution).

• sortList is not designed to deal with an empty list. It should check the case where head is null.

• In merge there will be an infinite loop when left->val==right->val. In that case the loop body doesn't do anything, and so the loop condition will remain unchanged. Related to this problem is that the second if condition could hit a null-pointer (left) when the first if block had executed at a moment left was the last node of that list. Both issues are solved if you make combine the two if blocks into an if ... else construct.

Not a problem, but:

• If tp is short for tail pointer, then you have inverted the use of dummy and tp. Your loop advances dummy to reference the tail of the already sorted part, while you leave tp pointing to the dummy node. It would make more sense if you had done the opposite, and left dummy referencing the dummy node, and tp the tail.

• As you already have a fast pointer that will reach the end of the list, there is no need to have separate code to find the end of the list (in sortList). Instead, just pass one argument to mergeSort and let fast help you to identify the tail (what you called high) of your list.

• In C++ you really should use nullptr instead of NULL

• At the end of merge, after the main loop, you don't need another loop to attach the remaining nodes. It suffices to just link the remainder to the tail of the sorted part. All the next links after that do not have to change.

• merge doesn't use the high parameter, nor does it need it.

Here is your code with all of the above taken into account and corrected:

// No need for unused head and high parameters; but return the node that becomes head
ListNode* merge(ListNode* left, ListNode* right) {
    // Note that the two given lists are disjoint: mid1->next is nullptr.
    ListNode* dummy = new ListNode(-1);
    ListNode* tp = dummy;
    while (right && left) {
        if (left->val < right->val){
            tp->next = left;
            tp = left; // tp is the tail of the sorted part
            left = left->next;
        } else { // Must be an ELSE block (mutually exclusive) 
            tp->next = right;
            tp = right;
            right = right->next;
        }
    }
    if (right == NULL) {
        // No need for a loop here: just attach the remainder:
        tp->next = left;
    } else { // Can be an ELSE block
        tp->next = right;
    }
    // Assigning to `head` serves no purpose (`head` was a call-by-value parameter)
    return dummy->next; // Instead: return the head of the sorted list
}

// No need for three parameters; but return the new head
ListNode* mergesort(ListNode* head){
    if (!head->next) return head; // Adapated condition (no need for high)
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next && fast->next->next){
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode* high = fast->next ? fast->next : fast; // Define high
    ListNode* mid = slow;
    ListNode* mid1 = mid->next;
    mid->next = nullptr; // Assign! And don't use NULL in C++
    head = mergesort(head); // Get the first node back
    mid1 = mergesort(mid1); // (idem)
    return merge(head, mid1); // Return the first node of the result
}


class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head) return head;
        // No need to get the tail node here
        return mergesort(head); // Return the new head
    }
};