#include <stdlib.h>
#include <stdio.h>

typedef struct Node Node;

struct Node {
    int data;
    Node *next;
};

void print(const Node *node)
{
    while (node) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    
    puts("$");
}

/*
 *      Sort linked list with quicksort; return new tail
 */

Node *quicksort(Node **head)
{
    // base cases: empty list and single node

    if (*head == NULL) return NULL;
    if ((*head)->next == NULL) return *head;
    
    // partition with *head as pivot

    Node *lt = NULL;        // less than pivot
    Node *ge = NULL;        // greater than or equal to pivot

    Node *node = (*head)->next;

    while (node) {
        Node *next = node->next;

        if (node->data < (*head)->data) {
            node->next = lt;
            lt = node;
        } else {
            node->next = ge;
            ge = node;
        }

        node = next;
    }
    
    // quick-sort recursively

    Node *ltail = quicksort(&lt);
    Node *gtail = quicksort(&ge);

    // rearrange lists: lt -> pivot -> ge

    (*head)->next = ge;
    
    if (gtail == NULL) gtail = *head;
  
    if (lt) {
        ltail->next = *head;
        *head = lt;
    }

    return gtail;
}

int main(void)
{
    Node node[10];
    Node *head = NULL;
    
    for (unsigned i = 0; i < 10; i++) {
        node[i].data = (7 + 3*i) % 10;
        node[i].next = head;
        head = &node[i];
    }
    
    print(head);
    quicksort(&head);
    print(head);    

    return 0;
}