LeetCode Sort List

class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode *h1 = NULL, *h2 = NULL, *cur = head;
        ListNode *tail1 = h1, *tail2 = h2;

        int count = 0;
        while (cur != NULL) {
            if (++count & 0x1) {
                if (h1 == NULL) {
                    tail1 = h1 = cur;
                } else {
                    tail1->next = cur;
                    tail1 = cur;
                }
            } else {
                if (h2 == NULL) {
                    tail2 = h2 = cur;
                } else {
                    tail2->next = cur;
                    tail2 = cur;
                }
            }
            cur = cur->next;
        }
        if (h1 != NULL) tail1->next = NULL;
        if (h2 != NULL) tail2->next = NULL;

        h1 = sortList(h1);
        h2 = sortList(h2);
        
        ListNode *new_head = NULL, *new_tail = NULL;
        
        while (h1 != NULL && h2 != NULL) {
            if (h1->val < h2->val) {
                cur = h1;
                h1 = h1->next;
            } else {
                cur = h2;
                h2 = h2->next;
            }
            if (new_head == NULL) {
                new_head = new_tail = cur;
            } else {
                new_tail->next = cur;
                new_tail = cur;
            }
        }
        while (h1 != NULL) {
            new_tail->next = h1;
            new_tail = h1;
            h1 = h1->next;
        }
        while (h2 != NULL) {
            new_tail->next = h2;
            new_tail = h2;
            h2 = h2->next;
        }
        return new_head;
    }
};

Merge Sort，时间不太理想，也许直接遍历链表获得其数目然后进行二分比较快，这样链表初期的划分工作量就大大减少了,改写了一下也没这么提高

class ListNode {
public:
   int val;
   ListNode *next;
   ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (head == NULL) return head;
        ListNode* cur = head;
        int count = 1;
        while ((cur = cur->next) != NULL) count++;


        return sortListN(head, count);
    }
    
    ListNode* sortListN(ListNode *head, int n) {
        if (n < 2) return head;
        ListNode *h1, *h2, *cur;
        int k = n >> 1;
        cur = head;
        while (--k) cur = cur->next;
        h1 = head;
        h2 = cur->next;
        cur->next = NULL;

        h1 = sortListN(h1, n>>1);
        h2 = sortListN(h2, n - (n>>1));

        return merge(h1, h2);
    }
    
    ListNode* merge(ListNode* h1, ListNode* h2) {
        ListNode *new_head = NULL, *new_tail = NULL, *cur;

        while (h1 != NULL && h2 != NULL) {
            if (h1->val < h2->val) {
                cur = h1;
                h1 = h1->next;
            } else {
                cur = h2;
                h2 = h2->next;
            }
            if (new_head == NULL) {
                new_head = new_tail = cur;
            } else {
                new_tail->next = cur;
                new_tail = cur;
            }
        }
        while (h1 != NULL) {
            new_tail->next = h1;
            new_tail = h1;
            h1 = h1->next;
        }
        while (h2 != NULL) {
            new_tail->next = h2;
            new_tail = h2;
            h2 = h2->next;
        }
        return new_head;
    }
};

 简化一下，dummyhead还是比较实用的：

/**
 * 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) {
        int len = 0;
        ListNode* cur = head;
        while (cur != NULL) {
            len++;
            cur = cur->next;
        }
        ListNode* res = mergeSort(head, len);
    }
    
    ListNode* mergeSort(ListNode* head, int len) {
        if (len == 0) {
            return NULL;
        }
        if (len == 1) {
            return head;
        }
        
        int mid = len/2;
        ListNode *prev = NULL, *node = head;
        
        for (int i=0; i<mid; i++) {
            prev = node;
            node = node->next;
        }
        
        prev->next = NULL;
        
        ListNode* head1 = mergeSort(head, mid);
        ListNode* head2 = mergeSort(node, len - mid);
        
        ListNode dummy(0);
        prev = &dummy;
        while (head1 != NULL && head2 != NULL) {
            if (head1->val < head2->val) {
                prev->next = head1;
                prev = head1;
                head1 = head1->next;
            } else {
                prev->next = head2;
                prev = head2;
                head2 = head2->next;
            }
        }
        
        if (head1 != NULL) {
            prev->next = head1;
        }
        if (head2 != NULL) {
            prev->next = head2;
        }
        
        return dummy.next;
    }
};