[C] linked list를 활용한 Merge Sort

www.notion.so/4ca8894af0be47988240c043eee8bd4c

💡 샘플미션

1. 미션 제목

2개의 리스트 합치기

2. 지시문

EDWITH CS50 강좌를 모두 수강한 여러분은 유능한 개발자로 회사에 소문이나 핵심 부서로 배치되었습니다. 핵심부서의 주요 임무 중 하나는 다른 부서의 업무를 종합하는 일입니다. 부서 배치 첫 업무로 A부서에서 수행한 업무와 B부서에서 수행한 업무를 합치는 일을 맡게 되었습니다.

A부서에서는 미국 지사들의 매출이 오름차순으로 정렬된 자료를 연결리스트 형태로 보내왔고, B부서에서는 한국 지사들의 매출이 오름차순으로 정렬된 자료를 연결리스트 형태로 보내왔습니다.

여러분의 업무는 이제 두 연결리스트를 하나의 연결리스트로 합치어 한국과 미국 지사들의 매출이 오름차순으로 정렬된 연결리스트를 만드시는 것입니다. 예를 들어, A부서에서 보내온 연결리스트가 2->6->9->10, B부서에서 보내온 연결리스트가 1->5->7->8->11 이라면 여러분이 만들 연결리스트는 1->2->5->6->7->8->9->10->11 이 되어야 합니다.

업무 수행을 위해 연결 리스트를 합치는 함수와 합쳐진 연결 리스트를 출력하는 함수를 만들어주세요.

 

/**
 * 연결 리스트의 형태는 아래와 같습니다.
 * struct ListNode {
 *     int sales;
 *     struct ListNode *next;
 * } ListNode;
 */


struct ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){
    // 함수를 채워주세요!
}

void append(ListNode* l, int data) {
    // 함수를 채워주세요.
void printMergedLinkedList(ListNode* list3) {
    // 함수를 채워주세요!
}

int main() {
ListNode* listA = (ListNode*)malloc(sizeof(ListNode));
ListNode* listB = (ListNode*)malloc(sizeof(ListNode));
listA->next = NULL;
listB->next = NULL;

append(listA, 2);
append(listA, 6);
append(listA, 9);
append(listA, 10);
printList(listA);

append(listB, 1);
append(listB, 5);
append(listB, 7);
append(listB, 8);
append(listB, 11);
printList(listB);

ListNode* result = mergeTwoLists(listA, listB);
printList(result);
}

main 함수에는 위와 같이 정렬된 연결 리스트 2개가 미리 만들어져 있다고 가정합니다. 여러분이 작성하신 함수 mergeTwoLists 함수, append 함수 그리고 printMergedLinkedList를 순서대로 호출하면 정렬된 결과 출력이 나오도록 작성해 주세요.

 

A 부서와 B 부서에서 보내는 연결리스트는 모두 오름차순으로 정렬되어 있는 상태이며, A 부서에서 보내온 리스트와 B 부서에서 보내온 리스트의 길이는 다를 수 있습니다.

 

입력값: 정렬된 2개의 연결리스트(Main 함수에 문제와 같이 선언되어 있다고 가정)출력값: 정렬된 리스트가 출력되게 해주세요.

 

위의 문제라면, 다음과 같이 출력 값이 나와야 합니다.

 

2 6 9 10

1 5 7 8 11

1 2 5 6 7 8 9 10 11

 

3. 핵심 개념

#연결리스트 #리스트 삽입 #리스트 합치기 #리스트 출력 #병합정렬

🔔 답안

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

typedef struct node {
    int data;
    struct node* next;
}ListNode;

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

    l1 = l1->next;
    l2 = l2->next;

    while (l1!=NULL && l2!=NULL) {
        if (l1->data <= l2->data) {
            pt->next = l1;
            l1 = l1->next;
        } else {
            pt->next = l2;
            l2 = l2->next;
        }
        pt = pt->next;
    }
    if (l1 != NULL)
        pt->next = l1;
    if (l2 != NULL)
        pt->next = l2;
    return head;
}

void append(ListNode* l, int data) {
    ListNode* item = (ListNode*)malloc(sizeof(ListNode));
    item->data = data;
    item->next = NULL;

    ListNode* temp = (ListNode*)malloc(sizeof(ListNode));    
    temp = l;
    while(temp->next != NULL) {
        temp=temp->next;
    }
    temp->next = item;
}

void printList(ListNode* l) {
    while(l->next != NULL) {
        printf("%d ", l->next->data);
        l = l->next;
    }
    printf("\n");
}

int main() {
    ListNode* listA = (ListNode*)malloc(sizeof(ListNode));
    ListNode* listB = (ListNode*)malloc(sizeof(ListNode));
    listA->next = NULL;
    listB->next = NULL;

    append(listA, 2);
    append(listA, 6);
    append(listA, 9);
    append(listA, 10);
    printList(listA);

    append(listB, 1);
    append(listB, 5);
    append(listB, 7);
    append(listB, 8);
    append(listB, 11);
    printList(listB);

    ListNode* result = mergeTwoLists(listA, listB);
    printList(result);
}