Merge sort for Linked List

Question

The merge sort code on Leetcode giving stack-overflow error.

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)

trincot · Accepted Answer · 2024-08-10 12:46:42Z

The problem is that the node that findMiddle returns is made the tail node of the left partition. This makes the left partition always longer than the right partition. This is a real problem when you start with a list that has just two nodes, as then the left partition will get both these nodes, while the right partition gets none of them. Consequently, the recursion on the left partition will be in the same state as you already were -- i.e. a list with 2 nodes doesn't get partitioned into a left partition that is smaller.

Take for example the linked list 1 → 2. The call to findMiddle with a reference to 1 will return a reference to node 2. sortList will make that node the tail of the left partition, setting the next pointer of that node to nullptr -- which was aready nullptr, so nothing changes. The left partition is thus also 1 → 2, and now you see you didn't make any progress: you're locked into an infinite recursion.

To solve this, make sure that if findMiddle is called on a list with an even number of nodes, it returns a reference to the node that sits at the end of the first half. So in the case of 1 → 2, it should return a reference to node 1, not node 2.

To make this happen, change this initialisation:

 ListNode *fast=head;

to this one:

 ListNode *fast=head->next;

With this change, it should work as intended.

Collectives™ on Stack Overflow

Merge sort for Linked List

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related