148. Sort List -M

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

A:

----------------------------merge sort   ---------------------------
First divide into two list, and merge them (append to the end of a new list) , which is of O(n) complexity.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(not head || not head->next)
           return head;
        //divide into two list
        ListNode* slow = head, *fast = head->next;
        while(not fast && fast->next)      // this is what you made mistake
        {
            slow = slow->next;
            fast = fast->next;
            if(fast)
                fast=fast->next;
        }
        auto p1 = sortList(slow->next);
        slow->next = NULL;
        auto p2 = sortList(head);
        return merge(p1,p2);
    }
private:
    ListNode* merge(ListNode* p1, ListNode* p2)
    {
        ListNode* pre = new ListNode(0);
        ListNode* tail = pre;
        while(p1 || p2)
        {
            if(not p1)
            {
                tail->next = p2;
                break;
            }
            if(not p2)
            {
                tail->next = p1;
                break;
            }
            if(p1->val <p2->val)
            {
                tail->next = p1;
                p1 = p1->next;
            }else{
                tail->next = p2;
                p2 = p2->next;
            }
            tail = tail->next;
        }
        return pre->next;
    }
};

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