# I cannot figure out what's wrong with my code. Please help!

• Hi there,

My code gets TLE when the test data is large, but works fine with small data. When testing on my own machine, the code seems to trap into some infinite loop (it does not terminate when test data is large). But since the code is recursive, it is hard for me to figure out what's going wrong.

What's interesting is, when I change the code from using mid->next as the end point of the left half to set mid->next = NULL and use NULL as the end point of the left half (unlink the left half and right half), the code got accepted (and even beats 95.5% C++). But I am really curious why my previous code does not work. Please help.

My original erroneous code:

``````class Solution {
ListNode* sortList(ListNode* begin, ListNode* end) {
if (begin->next == end) return begin;
ListNode *head, *mid, *tail;
head = mid = tail = begin;
while (tail != end && tail->next != end && tail->next->next != end) {
tail = tail->next->next;
mid = mid->next;
}
ListNode * first = sortList(begin, mid->next);
ListNode * second = sortList(mid->next, end);
while (first != mid->next && second != end) {
if (first->val < second->val) {
first = first->next;
} else {
second = second->next;
}
}
if (first != mid->next) {
while (first->next != mid->next) {
first = first->next;
}
first->next = end;
} else {
}

}
public:
ListNode* sortList(ListNode* head) {
if (head == NULL) return NULL;
}
};
``````

My "better than 95.5% C++" code

``````class Solution {
public:

ListNode* sortList(ListNode* begin) {
if (begin == NULL) return NULL;
if (begin->next == NULL) return begin;
ListNode *head, *mid, *tail;
head = mid = tail = begin;
while (tail != NULL && tail->next != NULL && tail->next->next != NULL) {
tail = tail->next->next;
mid = mid->next;
}
auto tmp = mid->next;
mid->next = NULL;
ListNode * first = sortList(begin);
ListNode * second = sortList(tmp);
while (first != NULL && second != NULL) {
if (first->val < second->val) {
first = first->next;
} else {
second = second->next;
}
}
if (first != NULL) {
} else {
}

}
};``````

• I figured it out. It is because I always check first against `mid->next`, but actually `mid->next` may be changed when sorting the second half. Therefore, the loop will never end. In order to make the original code work, just use another variable to save the value of `mid->next` before passing it to sort.

The corrected code:

``````class Solution {
ListNode* sortList(ListNode* begin, ListNode* end) {
if (begin->next == end) return begin;
ListNode *head, *mid, *tail;
head = mid = tail = begin;
while (tail != end && tail->next != end && tail->next->next != end) {
tail = tail->next->next;
mid = mid->next;
}
auto fend = mid->next; // use fend instead of mid->next, since mid->next can change
ListNode * first = sortList(begin, fend);
ListNode * second = sortList(fend, end);
while (first != fend && second != end) {
if (first->val < second->val) {
first = first->next;
} else {
second = second->next;
}
}
if (first != fend) {
while (first->next != fend) {
first = first->next;
}
first->next = end;
} else {
}

}
public:
ListNode* sortList(ListNode* head) {
if (head == NULL) return NULL;