/
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode next;
* };
/

typedef struct ListNode Node;

// Function to partition the list
struct ListNode partition(Node head, Node left, Node right){
if(head == NULL || head->next == NULL) return head;

Node* pivot = head; // Set the pivot as the head
Node* current = head->next;
Node* leftTail = NULL;
Node* rightTail = NULL;

// Iterate through the list and partition it into left and right
while(current != NULL){
    Node* next = current->next; // Save next node before detaching
    if(current->val < pivot->val){
        // Add to the left partition
        if(*left == NULL){
            *left = current;
            leftTail = current;
        } else {
            leftTail->next = current;
            leftTail = current;
        }
        leftTail->next = NULL; // Ensure left partition ends with NULL
    } else {
        // Add to the right partition
        if(*right == NULL){
            *right = current;
            rightTail = current;
        } else {
            rightTail->next = current;
            rightTail = current;
        }
        rightTail->next = NULL; // Ensure right partition ends with NULL
    }
    current = next; // Move to the next node
}

return pivot;

}

// Main quicksort function for linked list
struct ListNode quickSortList(struct ListNode head) {
if(head == NULL || head->next == NULL) return head;

Node* left = NULL;
Node* right = NULL;

// Partition the list
Node* pivot = partition(head, &left, &right);

// Recursively sort the left and right partitions
left = quickSortList(left);
right = quickSortList(right);

// Concatenate the sorted left partition, pivot, and sorted right partition
Node* tail = left;
if(left != NULL){
    while(tail->next != NULL) tail = tail->next;
    tail->next = pivot;
} else {
    left = pivot;
}

pivot->next = right;

return left;

}