<commit_before>/**
 * Description : Merge k Sorted Lists
 *               Merge k sorted lists and return it as one sorted list. Analyze
 *               and describeits complesity.
 * Author      : <NAME>
 * Date        : 2016/03/04
 */

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

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* mergeTwoLists(struct ListNode *l1, struct ListNode *l2)
{
    struct ListNode *p = l1;
    struct ListNode *q = l2;
    struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *ptr = head;
    struct ListNode *tmp = head;

    if (l1 == NULL && l2 != NULL)
    {
        return l2;
    }
    if (l1 != NULL && l2 == NULL)
    {
        return l1;
    }
    if (l1 == NULL && l2 == NULL)
    {
        return NULL;
    }

    if (p->val <= q->val)
    {
        ptr->val = p->val;
        p = p->next;
    }
    else
    {
        ptr->val = q->val;
        q = q->next;
    }

    while (p != NULL && q != NULL)
    {
        tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
        ptr->next = tmp;
        ptr = ptr->next;
        if (p->val <= q->val)
        {
            ptr->val = p->val;
            p = p->next;
        }
        else
        {
            ptr->val = q->val;
            q = q->next;
        }
    }

    if (p == NULL)
    {
        while (q != NULL)
        {
            tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
            ptr->next = tmp;
            ptr = ptr->next;
            ptr->val = q->val;
            q = q->next;
        }
    }

    if (q == NULL)
    {
        while (p != NULL)
        {
            tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
            ptr->next = tmp;
            ptr = ptr->next;
            ptr->val = p->val;
            p = p->next;
        }
    }

    ptr->next = NULL;

    return head;
}

struct ListNode* createList(int *nums, int numsSize)
{
    int cnt = 0;
    struct ListNode *head = NULL;
    struct ListNode *tmp = NULL;
    struct ListNode *cur = NULL;

    cur = (struct ListNode *)malloc(sizeof(struct ListNode));
    cur->val = nums[cnt++];
    head = cur;
    tmp =cur;
    numsSize--;

    while (numsSize--)
    {
        cur = (struct ListNode *)malloc(sizeof(struct ListNode));
        cur->val = nums[cnt++];
        tmp->next = cur;
        tmp = cur;
    }
    tmp->next = NULL;

    return head;
}

struct ListNode* sortList(struct ListNode *head)
{
    int tmp;
    struct ListNode *p = NULL;
    struct ListNode *q = NULL;

    for (p = head; p->next != NULL; p = p->next)
    {
        for (q = p->next; q != NULL; q = q->next)
        {
            if (p->val > q->val)
            {
                tmp = p->val;
                p->val = q->val;
                q->val = tmp;
            }
        }
    }

    return head;
}

void printList(struct ListNode *head)
{
    struct ListNode *tmp = head;

    while (tmp != NULL)
    {
        printf("%d->", tmp->val);
        tmp = tmp->next;
    }
    printf("NULL\n");
}

void freeList(struct ListNode *head)
{
    struct ListNode *p = head;
    struct ListNode *tmp = NULL;

    while (p != NULL)
    {
        tmp = p;
        p = p->next;
        free(tmp);
    }

    head = NULL;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
    struct ListNode* head = NULL;

    if (listsSize == 1)
    {
        return lists[0];
    }

    head = mergeTwoLists(lists[0], lists[1]);

    for (int i = 2; i < listsSize; i++)
    {
        head = mergeTwoLists(head, lists[i]);
    }

    return head;
}

int main(void)
{
    int arr1[5] = {5, 4, 3, 2, 1};
    int arr2[6] = {12, 8, 3, 7, 0, 9};
    int arr3[3] = {0, 0, 0};
    int arr4[6] = {5, 2, 5, 0, 1, 10};
    int arr5[4] = {-3, -3, -3, -1};
<commit_msg>Update #23<commit_after>/**
 * Description : Merge k Sorted Lists
 *               Merge k sorted lists and return it as one sorted list. Analyze
 *               and describeits complesity.
 * Author      : <NAME>
 * Date        : 2016/03/04
 */

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

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* mergeTwoLists(struct ListNode *l1, struct ListNode *l2)
{
    struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *cur = head;

    while (l1 && l2)
    {
        if (l1->val > l2->val)
        {
            cur->next = l2;
            l2 = l2->next;
        }
        else
        {
            cur->next = l1;
            l1 = l1->next;
        }
        cur = cur->next;
    }

    if (l1)
    {
        cur->next = l1;
    }
    else
    {
        cur->next = l2;
    }

    return head->next;
}

struct ListNode* merge(struct ListNode* lists[], int beg, int end)
{
    if (beg > end)
        return NULL;
    if (beg == end)
        return lists[beg];

    int mid = (beg + end) / 2;
    struct ListNode *left = merge(lists, beg, mid);
    struct Listnode *right = merge(lists, mid, end);

    return mergeTwoLists(left, right);
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
    return merge(lists, 0, k - 1);
}

struct ListNode* createList(int *nums, int numsSize)
{
    int cnt = 0;
    struct ListNode *head = NULL;
    struct ListNode *tmp = NULL;
    struct ListNode *cur = NULL;

    cur = (struct ListNode *)malloc(sizeof(struct ListNode));
    cur->val = nums[cnt++];
    head = cur;
    tmp =cur;
    numsSize--;

    while (numsSize--)
    {
        cur = (struct ListNode *)malloc(sizeof(struct ListNode));
        cur->val = nums[cnt++];
        tmp->next = cur;
        tmp = cur;
    }
    tmp->next = NULL;

    return head;
}

struct ListNode* sortList(struct ListNode *head)
{
    int tmp;
    struct ListNode *p = NULL;
    struct ListNode *q = NULL;

    for (p = head; p->next != NULL; p = p->next)
    {
        for (q = p->next; q != NULL; q = q->next)
        {
            if (p->val > q->val)
            {
                tmp = p->val;
                p->val = q->val;
                q->val = tmp;
            }
        }
    }

    return head;
}

void printList(struct ListNode *head)
{
    struct ListNode *tmp = head;

    while (tmp != NULL)
    {
        printf("%d->", tmp->val);
        tmp = tmp->next;
    }
    printf("NULL\n");
}

void freeList(struct ListNode *head)
{
    struct ListNode *p = head;
    struct ListNode *tmp = NULL;

    while (p != NULL)
    {
        tmp = p;
        p = p->next;
        free(tmp);
    }

    head = NULL;
}



int main(void)
{
    int arr1[5] = {5, 4, 3, 2, 1};
    int arr2[6] = {12, 8, 3, 7, 0, 9};
    int arr3[3] = {0, 0, 0};
    int arr4[6] = {5, 2, 5, 0, 1, 10};
    int arr5[4] = {-3, -3, -3, -1};

{'fraction_non_alphanumeric': 0.15010752688172044, 'fraction_numerical': 0.0182078853046595, 'mean_word_length': 1.6324528301886791, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 88, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4592852', 'n_tokens_mistral': 2529, 'n_tokens_neox': 2416, 'n_words': 677}