[leetcode]Sort List

題目要求：
Sort a linked list in?O(n?log?n) time using constant space complexity.

?數據結構定義：

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

這里用的數據結構是單鏈表。時間復雜度是O(n?log?n)的排序算法有：堆排序，快速排序，歸并排序。題目要求使用常量的空間復雜度，這三種排序方法的空間復雜度分別是O(n),O(1),O(n)[對于數組]。歸并排序的空間復雜度是O(n)，因為對于數組，歸并排序需要額外的O(n)的空間來處理數組，而對于鏈表而言，操作都是對指針的，所以可以將空間復雜度降到O(1)。

這里使用歸并排序來實現代碼。

?

/**
 * 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 (head == NULL)
            return head;
        else if (head->next == NULL) 
            return head;
        
        ListNode *slow = head, *fast = head;
        while (fast->next != NULL && fast->next->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        fast = slow;
        slow = slow->next;
        fast->next = NULL;
        
        fast = sortList(head);
        slow = sortList(slow);
        
        return mergeList(fast,slow);
        
    }
    ListNode* mergeList(ListNode* list1Head, ListNode* list2Head){
        if (list1Head == NULL) return list2Head;
        if (list2Head == NULL) return list1Head;
        
        ListNode* result, *temp;
        // initialize the first node of the merged result list
        if (list1Head->val < list2Head->val){
            result = list1Head;
            list1Head = list1Head->next;
        }
        else
        {
            result = list2Head;
            list2Head = list2Head->next;
        }
        // operate the result list with temp
        temp = result;
        // end merge if at least one of the two lists reaches the tail node
        while (list1Head != NULL && list2Head != NULL){
            if (list1Head->val < list2Head->val){
                temp->next = list1Head;
                list1Head = list1Head->next;
            }
            else{
                temp->next = list2Head;
                list2Head = list2Head->next;
            }
            temp = temp->next;
        }
        
        if (list1Head != NULL)
            temp->next = list1Head;
        else
            temp->next = list2Head;
            
        return result;
    }
};

這個簡單的OJ浪費了我大概半個多小時在調試BUG，實在有點太菜了。AC之前我的代碼遇到了下面幾個惡心的BUG。

1. 在找到鏈表的中間節點后，用head和slow來表示左右兩個子臉變的時候，沒有把中間節點的next指針置為空，導致程序無限遞歸，最后導致堆溢出。

2. 在合并排序數組的函數中，處理未添加到result鏈表中的節點（64~67）時，if語句條件寫錯了。....

.....

沉心學習，努力積累，希求爆發。

?