The merge sort code on Leetcode giving stack-overflow error.
<code>ListNode *findMiddle(ListNode *head){
if (!head) return nullptr;
ListNode *slow=head;
ListNode *fast=head;
while (fast!=nullptr && fast->next!=nullptr){
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
ListNode *merge(ListNode *left,ListNode *right ){
ListNode *dummy=new ListNode(-1);
ListNode *tmp=dummy;
while (left!=nullptr && right !=nullptr){
if (left->val <right->val){
tmp->next=left;
tmp=left;
left=left->next;
}
else {
tmp->next=right;
tmp=right;
right=right->next;
}
}
//remaining arrays
if (left) tmp->next=left;
else tmp->next=right;
ListNode* result = dummy->next;
delete dummy;
return result;
}
ListNode* sortList(ListNode* head) {
//base case
if (head==nullptr || head->next== nullptr ){
return head;
}
ListNode *middle=findMiddle(head);
ListNode *left=head;
ListNode *right=middle->next;
middle->next=nullptr;
left=sortList(left);
right=sortList(right);
return merge(left,right);
}
</code>
<code>ListNode *findMiddle(ListNode *head){
if (!head) return nullptr;
ListNode *slow=head;
ListNode *fast=head;
while (fast!=nullptr && fast->next!=nullptr){
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
ListNode *merge(ListNode *left,ListNode *right ){
ListNode *dummy=new ListNode(-1);
ListNode *tmp=dummy;
while (left!=nullptr && right !=nullptr){
if (left->val <right->val){
tmp->next=left;
tmp=left;
left=left->next;
}
else {
tmp->next=right;
tmp=right;
right=right->next;
}
}
//remaining arrays
if (left) tmp->next=left;
else tmp->next=right;
ListNode* result = dummy->next;
delete dummy;
return result;
}
ListNode* sortList(ListNode* head) {
//base case
if (head==nullptr || head->next== nullptr ){
return head;
}
ListNode *middle=findMiddle(head);
ListNode *left=head;
ListNode *right=middle->next;
middle->next=nullptr;
left=sortList(left);
right=sortList(right);
return merge(left,right);
}
</code>
ListNode *findMiddle(ListNode *head){
if (!head) return nullptr;
ListNode *slow=head;
ListNode *fast=head;
while (fast!=nullptr && fast->next!=nullptr){
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
ListNode *merge(ListNode *left,ListNode *right ){
ListNode *dummy=new ListNode(-1);
ListNode *tmp=dummy;
while (left!=nullptr && right !=nullptr){
if (left->val <right->val){
tmp->next=left;
tmp=left;
left=left->next;
}
else {
tmp->next=right;
tmp=right;
right=right->next;
}
}
//remaining arrays
if (left) tmp->next=left;
else tmp->next=right;
ListNode* result = dummy->next;
delete dummy;
return result;
}
ListNode* sortList(ListNode* head) {
//base case
if (head==nullptr || head->next== nullptr ){
return head;
}
ListNode *middle=findMiddle(head);
ListNode *left=head;
ListNode *right=middle->next;
middle->next=nullptr;
left=sortList(left);
right=sortList(right);
return merge(left,right);
}
Error:
Line 68: Char 26:
AddressSanitizer:DEADLYSIGNAL
=================================================================
==22==ERROR: AddressSanitizer: stack-overflow on address 0x7ffc38017ff8 (pc 0x565014054e8d bp 0x7ffc38018020 sp 0x7ffc38018000 T0)