<p>Given the <code>head</code> of a linked list, return <em>the list after sorting it in <strong>ascending order</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/14/sort_list_1.jpg" style="width: 450px; height: 194px;" />
<pre>
<strong>Input:</strong> head = [4,2,1,3]
<strong>Output:</strong> [1,2,3,4]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/14/sort_list_2.jpg" style="width: 550px; height: 184px;" />
<pre>
<strong>Input:</strong> head = [-1,5,3,4,0]
<strong>Output:</strong> [-1,0,3,4,5]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> head = []
<strong>Output:</strong> []
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the list is in the range <code>[0, 5 * 10<sup>4</sup>]</code>.</li>
	<li><code>-10<sup>5</sup> &lt;= Node.val &lt;= 10<sup>5</sup></code></li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> Can you sort the linked list in <code>O(n logn)</code> time and <code>O(1)</code> memory (i.e. constant space)?</p>

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

void help(ListNode* head, ListNode*& t1, ListNode*& t2) {
    if (!head)
        return;
    ListNode *slow = head, *fast = head->next;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    t2 = slow->next;
    slow->next = nullptr;
    t1 = head;
    return;
}

ListNode* help2(ListNode*& n1, ListNode*& n2) {
    if (!n1)
        return n2;
    if (!n2)
        return n1;
    ListNode* s;
    if (n1->val <= n2->val) {
        s = n1;
        s->next = help2(n1->next, n2);
    } else {
        s = n2;
        s->next = help2(n1, n2->next);
    }
    return s;
}

class Solution {
public:
    ListNode* sortList(ListNode*& head) {
        if (!head || !head->next) return head;
        ListNode *t1, *t2;
        help(head, t1, t2);
        if (t1)
            cout << t1->val << " t ";
        if (t2)
            cout << t2->val << " t ";
        cout << endl;
        // while(t1) {
        //     cout<<t1->val<<" ";
        //     t1 = t1->next;
        // }
        // cout<<endl;
        ListNode *sl1, *sl2;
        sl1 = sortList(t1);
        sl2 = sortList(t2);
        if (sl1)
            cout << sl1->val << " s ";
        if (sl2)
            cout << sl2->val << " s ";
        cout << endl;
        head = help2(sl1, sl2);
        return head;
    }
};
37103