单链表的快排

一个单链表无序数组，要求O(1)空间复杂度 O(nlogn)时间复杂度排序。

明显快排，但链表没写过，练手。

代码已验证，可运行，主体没有问题 ，但细节有一个小问题。手工开辟了个空的头结点，实际没有删除。这点需要改进。

 

#include <stdio.h>
#include <stdlib.h>
typedef struct tagNode{
    int value;
    struct tagNode* next;
}Node;

void outputLinkedList(Node * head){
    while(head!=NULL){
        printf("-->%d ",head->value);
        head = head->next;
    }
    printf("\n");
}

Node * createNode(int value){
    Node * ret = (Node*)malloc(sizeof(Node));
    ret->value = value;
    ret->next = NULL;
    return ret;
}
Node * createLinkedList(int *input, int size){
    Node* ret = NULL;
    int i = 0;
    Node *tmp = NULL;
    for(;i<size;i++){
        ret = createNode(input[i]);
        ret->next = tmp;
        tmp = ret;
    }
    return ret;
}

void swapvalue(Node * left, Node* right){
    if(left == NULL || right == NULL || left == right)
        return;

    (left->value)^=(right->value);
    (right->value)^=(left->value);
    (left->value)^=(right->value);
}
Node *partition(Node* start, Node* end){
    if(end == NULL) return start;
    if(start == NULL) return NULL;

    Node* low = (Node*)malloc(sizeof(Node));
    low->next = start;
    low->value = 10000;
    Node* high = start;
    int piv = end->value;
        printf("piv = %d \n", piv);
    while(high!=end){
        if(high->value<piv){
            low = low->next;
                        printf("swap %d %d\n",low->value, high->value);
            swapvalue(low,high);
        }
        high = high->next;
    }
    Node* ret = low;
    low = low->next;
    swapvalue(low,end);
    return ret;
}

void llqsort(Node* start, Node* end){
    if(start == NULL || end == NULL ||start == end || end->next == start) return ;
    Node* mid = partition(start, end);
    llqsort(start,mid);
    mid = mid->next;
    if(mid!=NULL)
        llqsort(mid->next, end);
}

Node* gettail(Node*head){
    if(head == NULL) return NULL;
    while(head->next!=NULL)
        head = head->next;
    return head;
}


int main(){
    int input[] = {1,3,5,2,6,4,2};
    Node* head = createLinkedList(input, sizeof(input)/sizeof(int));
    Node* tail = gettail(head);
    outputLinkedList(head);
        printf("tail = %d\n",tail->value);
    llqsort(head, tail);
    outputLinkedList(head);
}