#include <stdio.h>
#include <stdlib.h>
//노드 생성 → 리스트 생성 → 병합 함수 호출 → 결과 출력 → 메모리 해제


// 두 개의 오름차순 연결 리스트를 하나의 오름차순 리스트로 합병하기 위해 
// head와 rear 포인터를 어떻게 설정하고 남은 리스트를 어떻게 연결하는지 묻는 문제
// 연결리스트 [데이터|다음노드주소]
typedef struct node * NODE; //구조체타입의 노드 포인터

struct node{
    int id; //현재노드 값  
    NODE next; //다음 노드 
};

/* 노드 하나 생성 */
NODE createNode(int id) {
    NODE newNode = (NODE)malloc(sizeof(struct node));//노드공간 메모리에 동적할당받음

    if (newNode == NULL) {
        printf("메모리 할당 실패\n");
        exit(1);
    }

    newNode->id = id; //값설정
    newNode->next = NULL; //다음주소 NULL설정

    return newNode;
}

/* 리스트 맨 뒤에 노드 추가 */
NODE appendNode(NODE head, int id) {
    NODE newNode = createNode(id);

    if (head == NULL) {
        return newNode;
    }

    NODE cur = head;

    while (cur->next != NULL) {
        cur = cur->next;
    }

    cur->next = newNode;

    return head;
}

NODE  mergelist(NODE a, NODE b){
    NODE head = NULL, rear = NULL; //head: 결과 리스트의 첫 번째 노드, rear = 결과 리스트의 마지막 노드

    // 둘 중 하나가 처음부터 비어 있는 경우 처리 */
    if (a == NULL) {
        return b;
    }

    if (b == NULL) {
        return a;
    }  
    
    while(a != NULL && b != NULL){ //
        if(rear == NULL){ //병합리스트에 아직 첫 번째 노드를 정하지 않은 상태
            if(a->id < b->id){ //첫번째 리스트 노드가 두번째 리스트노드의 값보다 작으면 
                head = rear = a; //첫번째 노드=마지막노드=a
                a = a->next; //a를 다음노드로 이동(a 로인터가 다음노드를 가르키도로록 변경)               
            }else{ 
                head = rear = b;
                b = b->next;
            }
        } else { //병합리스트에 노드가 하나 이상 있는 상태, head  변경불가
            if(a->id < b->id){
                rear->next = a; //결과리스트 뒤에 새로운 노드 a 붙이기
                rear = rear->next; //rear를 다음 노드로 옮기기
                a = a->next; //a를 다음노드로 이동
            }else{
                rear->next = b;
                rear = rear->next;
                b = b->next;
         }
     }
}
    if(a == NULL && b!= NULL){ //a 리스트가 먼저 끝나고, b리스트가 남아 있는 상태
        rear->next = b; //병합리스트 뒤에 b 붙이기
    }else if(a != NULL && b == NULL){ //b리스트가 먼저 끝나고, a리스트가 남아 있는 상태
        rear->next = a; //병합리스트 뒤에 a 붙이기     
    }
    return head;
}

//병합함수가 제대로 되었는지 확인하기 위해서 출력함수 추가 
//기존 노드들을 새 순서로 사용하여 다시 연결 -> a,b free()하면 안되고, 최종결과만 해제
void printList(NODE head) {
    while (head != NULL) {
        printf("%d", head->id);

        if (head->next != NULL) {
            printf(" -> ");
        }

        head = head->next;
    }

    printf(" -> NULL\n");
}

/* 리스트 메모리 해제 */
void freeList(NODE head) {
    NODE temp;

    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

int main(void) {
    NODE a = NULL;
    NODE b = NULL;
    NODE result = NULL;

    /* a 리스트 생성: 3 -> 8 -> 15 */
    a = appendNode(a, 3);
    a = appendNode(a, 8);
    a = appendNode(a, 15);

    /* b 리스트 생성: 4 -> 7 -> 21 */
    b = appendNode(b, 4);
    b = appendNode(b, 7);
    b = appendNode(b, 21);

    printf("a 리스트: ");
    printList(a);

    printf("b 리스트: ");
    printList(b);

    result = mergelist(a, b);

    printf("병합 결과: ");
    printList(result);

    freeList(result);

    return 0;
}