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

typedef struct {
    int val;
    struct Node *next;
} Node;

//without Eglot's Tab is great
Node *reverseList(Node *head) {
    if (head == NULL) return NULL;

    Node* prev = NULL;
    Node* curr = head;
    Node* next = NULL;
    //Just Draw A Graph. Solved!
    while(curr != NULL){
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}

Node* iter_merge_by_sort_greater(Node* head1, Node* head2){
    if(head1 == NULL) return head2;
    if(head2 == NULL) return head1;
    Node* i = head1;
    Node* j = head2;
    Node* curr = (head1->val > head2->val) ? head2 : head1;
    
    while(i != NULL && j != NULL){
        if(i->val > j->val){
            curr->next = j;
            j = j->next;
        } else {
            curr->next = i;
            i = i->next;
        } 
    }
    while(i != NULL){
        curr->next = i;
        i = i->next;
    }
    while(j != NULL){
        curr->next = j;
        j = j->next;
    }
    return curr;
}

Node* recursion_merge_sort_by_greater(Node* head1, Node* head2, Node* curr, Node* start){
    if(head1 == NULL && head2 == NULL) return NULL;
    //check NULL
    if(head1 && head2){
        if(head1->val > head2->val) {
            curr->next = head2;
            head2 = head2->next;
            recursion_merge_sort_by_greater(head1, head2, curr, start);
        }
        else{
            curr->next = head1;
            head1 = head1->next;
            recursion_merge_sort_by_greater(head1, head2, curr, start);
        }
    }
    if(head1){
        curr->next = head1;
        head1 = head1->next;
        recursion_merge_sort_by_greater(head1, NULL, curr, start);
    }
    if(head2){
         curr->next = head2;
            head2 = head2->next;
            recursion_merge_sort_by_greater(NULL, head2, curr, start);
    }

    return start;
}

int main() {
    
    return 0;
}