합병 정렬 관련해서 질문하고 싶습니다

조회수 2493회

학교에서 합병정렬 관련해서 아래와 같은 문제를 받았습니다.(언어는 C입니다.)

이미지

이미지

아래의 알고리즘을 참고해서 배열이 아닌 연결리스트로 구현하라고 하여서 구현하려는 것 까지는 좋았는데

구현해야할 합병 알고리즘에 있는 조건 3번째에 "합병을 위해서 새로운 공간을 할당하면 안되고, L1과 L2의 노드들의 링크만 변화시켜서 합병하라"고 되어있어서 이를 어떻게 구현해야할지 몰라서 질문하게 되었습니다.

저는 아래처럼 merge는 아직 짜지 못한 상태입니다. (merge 로 인해서 아직 main 문 또한 완성하지 못한 상태입니다.)

typedef struct ListNODE {

int data;
struct ListNODE *next;

}listNode;

typedef struct LinkedList_h {

listNode *head;

}linkedList_h;

linkedList_h *createLinkedList_h(void) {

linkedList_h *List;

List = (linkedList_h *)malloc(sizeof(linkedList_h));
List->head = NULL;

return List;

}

linkedList_h *L; linkedList_h *L1; linkedList_h *L2; int N;

void input_data(linkedList_h *List, int num) {

listNode *newNode;
listNode *temp;

newNode = (listNode *)malloc(sizeof(listNode));

newNode->data = num;
newNode->next = NULL;

if (List->head == NULL)
{
    List->head = newNode;
    return;
}
else
{
    temp = List->head;

    while (temp->next != NULL)
        temp = temp->next;

    temp->next = newNode;
}

}

void printList(linkedList_h *List) {

listNode *temp;

temp = (listNode *)malloc(sizeof(listNode));

temp = List->head;

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

}

void mg_partition(int l, int m, int r) {

int i;
listNode *temp;
L1 = createLinkedList_h();
L2 = createLinkedList_h();

temp = L->head;

for (i = 0; i < l; i++)
    temp = temp->next;

for (i = l; i <= r; i++)
{
    if (i <= m)
    {
        input_data(L1, temp->data);

        temp = temp->next;
    }
    else
    {
        input_data(L2, temp->data);

        temp = temp->next;
    }
}

}

void merge(linkedList_h *List, int l, int m, int r) {

}

void rMergeSort(linkedList_h *List, int l, int r) {

int m;

if (l < r)
{
    m = (l + r) / 2;

    rMergeSort(L, l, m);
    rMergeSort(L, m + 1, r);

    merge(L, l, m, r);
}

}

void mergeSort(linkedList_h *List) {

rMergeSort(L, 0, N - 1);

printList(L);

}

void main() {

int i, num;

L = createLinkedList_h();


scanf("%d", &N);

for(i=0 ; i<N ; i++)
{
    scanf("%d", &num);

    input_data(L, num);
}

printList(L);

}

merge 함수 짜는 것을 도움받거나 힌트를 얻고 싶습니다. 그리고 다른 함수 부분 짜는 것이 더욱 바람직한 방법이 있다면 조언을 구하고 싶습니다. 잘 부탁드립니다.

  • (•́ ✖ •̀)
    알 수 없는 사용자

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)