148. Sort List ---- Medium !!!!!!!

Given the head of a linked list, return the list after sorting it in ascending order.

 

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

 

Constraints:

• The number of nodes in the list is in the range [0, 5 * 104].
• -105 <= Node.val <= 105

 

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

A:

insertion sort, 会超时

----------------------------merge sort   ---------------------------

/**

* 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) {}

* };

*/

class Solution {

public:

ListNode* sortList(ListNode* head) {

if(!head || !head->next)

return head;

ListNode * slow = head, *fast = head->next;

while(fast && fast->next){

slow = slow->next;

fast = fast->next->next;

}

auto l1 = sortList(slow->next);

slow->next = nullptr;

auto l2 = sortList(head);

// merge two list

ListNode header;

auto tail = &header;

while(l1 && l2){

ListNode * tmp;

if(l1->val <= l2->val ){

tmp = l1;

l1 = l1->next;

}else{

tmp = l2;

l2 = l2->next;

}

tmp->next = nullptr;

tail->next = tmp;

tail = tail->next;

}

if(l1)

tail->next = l1;

else if(l2)

tail->next = l2;

return header.next;

}

};

----------- For follow up question:   quick sort --------------------

但是依然LTE了 ？？？？？？？？？？？

原因在于，如果是在最坏的情况，数组本来就是倒叙的。

暂时没有什么很好的解决方法。 （数组的形式，可以很方便用首尾的平均值）  还是用merge sort来解决这个问题吧。

/**

* 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) {}

* };

*/

class Solution {

public:

ListNode* sortList(ListNode* head) {

// quick sort

if(not head || not head->next)

return head;

ListNode h1(INT_MIN), h2(INT_MIN);

int pivot = head->val;

ListNode* runner = head->next; // do not include head when generating

while(runner){

auto tmp = runner;

runner = runner->next;

tmp->next = nullptr;

if(tmp->val <= pivot){

tmp->next = h1.next;

h1.next = tmp;

}else{

tmp->next = h2.next;

h2.next = tmp;

}

}

auto h_small = sortList(h1.next);

auto h_big = sortList(h2.next);

head->next = h_big;

if(not h_small)

return head;

// append h2 to h1;

runner = h_small;

while( runner->next){

runner = runner->next;

}

runner->next = head;

return h_small;

}

};

Mistakes: 

2: when updating runner after a while loop, always remember to set runner= runner.next; after extracting Header2 list.

 3: Coz we forget updating the tail  even after we already done inserting the list.
 4:  日！！！！！！
 刚开始， return 命令行上面的一句：         header= newHeader; 应该写成
        header.next = newHeader.next;  就对了。
╮(╯▽╰)╭， 基础不行啊。Tiger ，这种SB的问题，你都能犯~~~~~~ 搞了爷们儿2个小时。 艹


Learned:
1: in C++,  to judge whether a node is null, we have 3 method
       a)  node == NULL
       b)  ! node
       c) not node

2: 

quick sort 最大的trick就是，每次要把pivot摘下来，放到中间。 这样可以保证每次都变小。

3: linkedlist ，摘下一个节点的时候

auto tmp = runner;

runner = runner->next;

tmp->next = nullptr;

顺序不能乱。 主要是第二行和第三行，要注意，顺序不能错。