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);
ListNode tmpHead(0), *tmpHeadPtr = &tmpHead;
while (first != mid->next && second != end) {
if (first->val < second->val) {
tmpHeadPtr->next = first;
first = first->next;
} else {
tmpHeadPtr->next = second;
second = second->next;
}
tmpHeadPtr = tmpHeadPtr->next;
}
if (first != mid->next) {
tmpHeadPtr->next = first;
while (first->next != mid->next) {
first = first->next;
}
first->next = end;
} else {
tmpHeadPtr->next = second;
}
return tmpHead.next;
}
public:
ListNode* sortList(ListNode* head) {
if (head == NULL) return NULL;
return sortList(head, 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);
ListNode tmpHead(0), *tmpHeadPtr = &tmpHead;
while (first != NULL && second != NULL) {
if (first->val < second->val) {
tmpHeadPtr->next = first;
first = first->next;
} else {
tmpHeadPtr->next = second;
second = second->next;
}
tmpHeadPtr = tmpHeadPtr->next;
}
if (first != NULL) {
tmpHeadPtr->next = first;
} else {
tmpHeadPtr->next = second;
}
return tmpHead.next;
}
};
```