[Leetcode] 23. Merge k Sorted Lists

Identifying the Problem

다수의 linked list를 하나로 연결하고, 오름차순 정렬한다.

 

Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] 

Organizing thoughts

1. listsSize -1 번 만큼 반복하며, list를 연결시킨다.

2. 하나로 연결시킨 linked list를 오름차순 정렬한다. 

Sourcecode

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{

    int i = 0;
    int j = 0;    
    int k = 0;
    int count = 0;
    int swap_num;

    if(listsSize == 0) return NULL; //아무것도 없는 경우 NULL 

    struct ListNode* swap; //버블 정렬용 포인터
    
    for(int i=0 ; i<listsSize-1; i++) //버블sort를 사용해 NULL포인터를 다 뒤로 밀어버린다.
    {
        for(int j=0; j<listsSize-1-i;j++)
        {   
            if(lists[j] == NULL)
            {
                swap = lists[j];
                lists[j] = lists[j+1];
                lists[j+1] = swap;
            }
        }
    }
    
    struct ListNode* tmp = lists[0];
    struct ListNode* ans = lists[0];


    while(tmp) //listSize만큼의 노드를 하나로 연결시킨다.
    {
        if(tmp->next == NULL && i < listsSize-1)
            tmp->next = lists[++i];

        tmp = tmp->next;
        count++; //count는 val이 들어있는 노드의 총 개수
    }



    while(k < count-1) //linked list 오름차순 버블정렬
    {
        struct ListNode* tmp = lists[0];

        while(tmp->next)
        {
            if(tmp->val > tmp->next->val)
            {
                swap_num = tmp->val;
                tmp->val = tmp->next->val;
                tmp->next->val = swap_num;
            }
            tmp = tmp->next;
        }

        k++;
    }
    
    return ans;
}

Mistake

testcase : [[],[-1,5,11],[],[6,10]] 같은 경우
NULL이 중간중간 껴 있어서, 연결이 불완전하게 되는 경우가 생겼다.
이 부분을 놓쳤다.