LeetCode Sort List（链表快速排序）

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

看到O(n log n)这个复杂度就想到了快速排序法。快速排序法主要思想为取一个基准点，采用交换+分治法完成快速排序。

对于单链表的快速排序，不能从后面开始遍历，因为根据后继找不到其前驱。因此采用以下步骤：

1.取每次的头节点为基准节点，然后将这个节点从链表分离出来。用两个指针，从头节点的下一个节点遍历。

2.找到一个小于头节点的值，若是第一个小于头节点的值，左链表的头指向它，然后继续遍历，满足小于就挂载在左链表的后面。相反，创建一个有链表。其实还是在原链表上创建。

3.使用递归分别对左链表和右链表进行如上操作，当头节点为NULL时，递归返回。当左右链表都返回时，将原来的头节点与左右链表挂上。

/**
 * 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;
        }
        ListNode* tail = NULL;
        for (tail = head; tail -> next; tail = tail -> next);
        quicksort(head, tail);
        return head;
    }
    
    void quicksort(ListNode* &head, ListNode* &tail) {
        if (head == NULL) {
            return;
        }
        int key = head -> val;
        ListNode* p = head -> next;
        head -> next = NULL;
        ListNode* left_front = NULL, *right_front = NULL;
        ListNode* left_head = NULL, *left_tail = NULL;
        ListNode* right_head = NULL, *right_tail = NULL;
        
        while (p) {
            if (p -> val < key) {  // 与头节点的值判断
                if (!left_head) {  // 左链表
                    left_head = p;
                    left_front = p;
                }
                else {
                    left_front -> next = p;
                    left_front = p;
                }
                p = p -> next;
                left_front -> next = NULL;
            }
            else {
                if (!right_head) { // 右链表
                    right_head = p;
                    right_front = p;
                }
                else {
                    right_front -> next = p;
                    right_front = p;
                }
                p = p -> next;
                right_front -> next = NULL;
            }
        }
        left_tail = left_front;
        right_tail = right_front;
        
        quicksort(left_head, left_tail); // 左链表递归
        quicksort(right_head, right_tail);// 右链表递归
        // 左右链表递归返回，将原先头节点挂在左右链表
        if (left_tail && right_head) { // 左右链表都为NULL
            left_tail -> next = head;
            head -> next = right_head;
            head = left_head;
            tail = right_tail;
        }
        else if (left_tail) {  // 右链表为NULL
            left_tail -> next = head;
            tail = head;
            head = left_head;
        }
        else if (right_head) {  // 左链表为NULL
            head -> next = right_head;
            tail = right_tail;
        }
    } 
};