My Accepted C solution using Linked List


  • 0
    O
    // using linked list since it is the easiest way of inserting a new element without memory copy
    /**
     * Return an array of arrays of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    typedef struct LinkedNode {
        int height;
        int position;
        struct LinkedNode* next;
    } list;
     
    int cmpfunc(const int* first, const int *second){
        int* a = *(const int**) first;
        int* b = *(const int**) second;
        if(a[0] > b[0]) return 0;
        else if(a[0] < b[0]) return 1;
        else{
            return (a[1] < b[1]? 0 : 1);
        }
    }
    int** reconstructQueue(int** people, int peopleRowSize, int peopleColSize, int* returnSize) {
        int** result = (int**)malloc(sizeof(int*)*peopleRowSize);
        qsort(people, peopleRowSize, sizeof(int*), cmpfunc);
        *returnSize = peopleRowSize;
        list* head = (list*)malloc(sizeof(list));
        head->height = 0;
        head->position = 0;
        head->next = NULL;
        int i;
        
        // this for loop is used to sort the given queue, put the highest person ahead, and the second highest person will natually stand based on its position value
        for(i = 0; i < peopleRowSize; i++){
            list* tmp = head;
            //printf("%d\n", people[i][1]);
            int j;
            for(j = 0; j < people[i][1]; j++){
                //printf("j = %d\n", j);
                tmp = tmp->next;
            }
            list* tmp2 = (list*)malloc(sizeof(list));
            tmp2->height = people[i][0];
            tmp2->position = people[i][1];
            tmp2->next = tmp->next;
            tmp->next = tmp2;
        }
        for(i = 0; i < peopleRowSize; i++){
            result[i] = (int*)malloc(sizeof(int)*2);
            result[i][0] = head->next->height;
            result[i][1] = head->next->position;
            head = head->next;
        }
        return result;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.