Merge two sorted linked lists

[Data Structures/Linked List/Easy]

https://www.hackerrank.com/challenges/merge-two-sorted-linked-lists/problem

Merge two sorted linked lists | HackerRank

 

두 개의 정렬된 연결리스트를 입력받는다.

처음에는 두 연결리스트가 정렬된 연결리스트인지 모르고 두 연결리스트를 먼저 병합하고 정렬하려고 했는데 뭔가 계속 wrong answer가 나와서 다른 방법으로 접근했다. 

두 정렬된 리스트가 null이 아니라는 조건하에 최종 병합된 연결리스트를 가리킨 merge의 첫 번째를 head1, head2 (cur1, cur2) 중 작은 값을 저장하게 한다. 그리고 이전 노드를 가리키게 할 prev에 merge를 저장하고 시작한다.

while문도 이와 같은 원리로 반복실행되도록 한다. 각 head1과 head2를 순차탐색하며 현재의 위치를 가리키는 cur1과 cur2이 null이 된다면 두 연결리스트의 원소들(노드들) 중 마지막 노드의 값이 다른 연결리스트의 노드들보다 작은 것으로 while문은 종료되고 null이 아닌 연결리스트의 나머지 부분을 덧붙인다.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();

typedef struct SinglyLinkedListNode SinglyLinkedListNode;
typedef struct SinglyLinkedList SinglyLinkedList;

struct SinglyLinkedListNode {
    int data;
    SinglyLinkedListNode* next;
};

struct SinglyLinkedList {
    SinglyLinkedListNode* head;
    SinglyLinkedListNode* tail;
};

SinglyLinkedListNode* create_singly_linked_list_node(int node_data) {
    SinglyLinkedListNode* node = malloc(sizeof(SinglyLinkedListNode));

    node->data = node_data;
    node->next = NULL;

    return node;
}

void insert_node_into_singly_linked_list(SinglyLinkedList** singly_linked_list, int node_data) {
    SinglyLinkedListNode* node = create_singly_linked_list_node(node_data);

    if (!(*singly_linked_list)->head) {
        (*singly_linked_list)->head = node;
    } else {
        (*singly_linked_list)->tail->next = node;
    }

    (*singly_linked_list)->tail = node;
}

void print_singly_linked_list(SinglyLinkedListNode* node, char* sep, FILE* fptr) {
    while (node) {
        fprintf(fptr, "%d", node->data);

        node = node->next;

        if (node) {
            fprintf(fptr, "%s", sep);
        }
    }
}

void free_singly_linked_list(SinglyLinkedListNode* node) {
    while (node) {
        SinglyLinkedListNode* temp = node;
        node = node->next;

        free(temp);
    }
}

// Complete the mergeLists function below.

/*
 * For your reference:
 *
 * SinglyLinkedListNode {
 *     int data;
 *     SinglyLinkedListNode* next;
 * };
 *
 */
SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    SinglyLinkedListNode *cur1=head1, *cur2=head2, *merge=NULL, *prev=NULL;
    if(cur1 && cur2){
        if(cur1->data <= cur2->data) {
            merge = cur1;
            cur1=cur1->next;
        }
        else{
            merge=cur2;
            cur2=cur2->next;
        }
        prev=merge;
    }

    while(cur1 && cur2){
        if(cur1->data <= cur2->data){
            prev->next= cur1;
            cur1=cur1->next;
        }
        else{
            prev->next=cur2;
            cur2=cur2->next;
        }
        prev=prev->next;
    }
    if(cur1 && !cur2)   prev->next=cur1;
    else if(!cur1 && cur2)  prev->next=cur2;
    return merge;
   
}

int main()