LeetCode/solutions/148. Sort List.md

# [148. Sort List](https://leetcode.com/problems/sort-list/)
# 思路
常见排序方法有插入排序，选择排序，堆排序，快速排序，冒泡排序，归并排序，桶排序等等。
但是时间复杂度为O(nlgn)只有快速排序，归并排序，堆排序, 而根据单链表的特点，最适于用归并排序(因为没法按索引访问元素所以快排不行, 而堆排序需要建堆空间不满足)。

## 思路一 归并排序递归版
归并排序的基本思想就是用递归: 
核心其实是分治法 Divide and Conquer，就是将链表从中间断开分成两部分，左右两边再分别调用排序的递归函数sortList，得到各自有序的链表后，再进行merge, 
当拆到链表只有一个结点时，无法继续拆分了，而此时只包含一个结点的链表一定是有序的(即递归出口). 我们可以用快慢指针法找到链表的中点. 

## 思路二 自底向上归并排序(非递归)
思路一由于使用了递归, 所以严格来讲空间复杂度是不满足要求的. 思路一是采用的自顶向下递归进行的, 而如果我们采用自底向上进行归并排序的话就不需要递归调用了.

整个流程是: 初始时把每个节点当做一个有序链表, 然后两两进行归并, 这样每两个节点就是有序的; 然后再将两个包含两个节点的有序子链表进行归并, 这样每四个就是有序的, 
这样一直迭代下去直到整个链表都是有序的.

# C++
## 思路一
``` C++
class Solution {
private:
    ListNode* merge(ListNode* p1, ListNode* p2){
        ListNode* head = new ListNode(-1);
        // head -> next = NULL;
    
        ListNode *p = head;
        while(p1 && p2){
            if(p1 -> val <= p2 -> val){
                p -> next = p1;
                p1 = p1 -> next;
            }
            else{
                p -> next = p2;
                p2 = p2 -> next;
            }
            p = p -> next;
        }
        p -> next = NULL;
        if(p1) p -> next = p1;
        else if(p2) p -> next = p2;

        return head -> next;
    }
public:
    ListNode* sortList(ListNode* head) {
        if(head == NULL || head -> next == NULL) return head;
        
        ListNode *fast = head, *slow = head, *pre_slow;
        while(fast && fast -> next){
            fast = fast -> next -> next;
            pre_slow = slow;
            slow = slow -> next;
        }
        pre_slow -> next = NULL;
        return merge(sortList(head), sortList(slow));
    }
};
```

## 思路二
``` C++
/**
 * 自底向上归并排序
 * 参考https://leetcode.com/problems/sort-list/discuss/46712/Bottom-to-up(not-recurring)-with-o(1)-space-complextity-and-o(nlgn)-time-complextity
*/
class Solution {
private:
    // 将链表分成两部分, 第一部分包含n个节点, 注意返回的是第二个链表的头
	ListNode* split(ListNode *head, int n){
		for(int i = 1; head && i < n; i++) head = head->next;
		
		if(!head) return NULL;
		ListNode *second = head->next;
		head->next = NULL;
		return second;
	}

    // merge两个有序链表, 并将merge后的链表接在head后面, 返回的是结果链表的最后一个节点
	ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head){
		ListNode *cur = head;
		while(l1 && l2){
			if(l1->val > l2->val){
				cur->next = l2;
				cur = l2;
				l2 = l2->next;
			}
			else{
				cur->next = l1;
				cur = l1;
				l1 = l1->next;
			}
		}
		cur -> next = (l1 ? l1 : l2);
		while(cur->next) cur = cur->next;
		return cur;
	}
    
public:
	ListNode *sortList(ListNode *head) {
		if(!head || !(head->next)) return head;
		
		// 获得链表长度
		ListNode* cur = head;
		int length = 0;
		while(cur){
			length++;
			cur = cur->next;
		}
		
		ListNode *dummy = new ListNode(-1);
		dummy -> next = head;
		ListNode *left, *right, *tail;
		for(int step = 1; step < length; step <<= 1){ // 左移1位比乘2要快
			cur = dummy -> next;
			tail = dummy;
			while(cur){
				left = cur;
				right = split(left, step);
				cur = split(right,step);
				tail = merge(left, right, tail);
			}
		}
		return dummy -> next;
	}
};
```