sort with avl

avl.c

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
struct TNode{
    struct ListNode *node;
    struct TNode *left;
    struct TNode *right;
    int height;
};

struct TNode* RR(struct TNode* k1)
{
    struct TNode* k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    
    int k1_l_height = (k1->left == NULL)? -1 : k1->left->height;
    int k1_r_height = (k1->right == NULL)? -1 : k1->right->height;
    int k2_r_height = (k2->right == NULL)? -1 : k2->right->height;
    
    k1->height = (k1_l_height >= k1_r_height)? k1_l_height +1 : k1_r_height + 1;
    k2->height = (k2_r_height >= k1->height)? k2_r_height +1 : k1->height + 1;
    return k2;
}

struct TNode* LL(struct TNode* k3)
{
    struct TNode* k2 = k3->left;
    k3->left = k2->right;
    k2->right = k3;
    
    int k3_l_height = (k3->left == NULL)? -1 : k3->left->height;
    int k3_r_height = (k3->right == NULL)? -1 : k3->right->height;
    int k2_l_height = (k2->left == NULL)? -1 : k2->left->height;
    
    k3->height = (k3_l_height >= k3_r_height)? k3_l_height +1 : k3_r_height + 1;
    k2->height = (k2_l_height >= k3->height)? k2_l_height +1 : k3->height + 1;
    return k2;
}

struct TNode* LR(struct TNode* k3)
{
    k3->left = RR(k3->left);
	return LL(k3);
}

struct TNode* RL(struct TNode* k1)
{
    k1->right = LL(k1->right);
	return RR(k1);
}

struct TNode* insert(struct TNode* tree, struct ListNode *node)
{

    if(tree == NULL)
    {
        struct TNode* tnode = (struct TNode*)malloc(sizeof(struct TNode));
        tnode->left = NULL;
        tnode->right = NULL;
        tnode->height = 0;
        tnode->node = node;
        tree = tnode;
    }
    else
    {
        if(tree->node->val >= node->val)
        {
            tree->left = insert(tree->left, node);
        }
        else
        {
            tree->right = insert(tree->right, node);
        }
        
        int lt_height = (tree->left == NULL)? -1 : tree->left->height;
        int rt_height = (tree->right == NULL)? -1 : tree->right->height;
        
        tree->height = (rt_height > lt_height) ? rt_height + 1 : lt_height + 1;
        if((lt_height - rt_height) == 2)
        {
            if(tree->left->node->val >=  node->val)
            {
                //LL
                //   3
                //  2
                // 1
                tree = LL(tree);
            }
            else
            {
                //LR
                //   3
                //  1
                //   2
                tree = LR(tree);
            }
        }
        if((lt_height - rt_height) == -2)
        {
            if(tree->right->node->val >=  node->val)
            {
                //RL
                //  1
                //   3
                //  2
                printf("%d ", tree->right->node->val);
                tree = RL(tree);
            }
            else
            {
                //RR                
                // 1
                //  2
                //   3
                tree = RR(tree);
            }
        }
    }
    
    return tree;
}

void findNext(struct TNode** min, struct TNode* tnode)
{
    if(tnode->left != NULL)
        findNext( min, tnode->left);
    if(*min == tnode) ;
    else
    {
        tnode->node->next = NULL;
        (*min)->node->next = tnode->node;
        *min = tnode;
    }
    if(tnode->right != NULL)
        findNext( min, tnode->right);
}
struct TNode* findMin(struct TNode* root)
{
    while(root->left)
    {
        root = root->left;
    }
    return root;
}
void sort(struct TNode* root, struct ListNode** head)
{
    struct TNode* min = findMin(root);
    *head = min->node;
    findNext(&min, root);
}
struct ListNode* sortList(struct ListNode* head) {
    if(head == NULL) return head;
    struct TNode* root = NULL;
    do
    {
        root  = insert(root, head);
    }
    while(head = head->next);
    struct ListNode* result = NULL;
    sort(root, &result);
    return result;
}