Merge two sorted linked lists

주어진 두 개의 정렬된 연결 리스트(Linked List)를 병합하여 하나의 정렬된 연결 리스트로 합치는 알고리즘 문제입니다. 이 문제의 목표는 두 연결 리스트를 정렬된 순서로 병합하여 새로운 연결 리스트를 반환하는 것입니다.

연결 리스트는 데이터 요소(Node)로 이루어진 데이터 구조로, 각 노드는 데이터와 다음 노드를 가리키는 링크(또는 포인터)로 구성됩니다. 연결 리스트의 끝을 나타내는 노드는 다음 노드를 가리키는 링크가 없는 특별한 노드일 수 있습니다.

문제 설명:
문제의 입력으로는 두 개의 정렬된 연결 리스트 head1과 head2가 주어집니다. 이 두 연결 리스트를 정렬된 순서로 병합하여 하나의 정렬된 연결 리스트를 생성해야 합니다.

알고리즘 절차:

두 연결 리스트를 동시에 순회하면서 각 노드의 데이터를 비교합니다.
두 노드의 데이터 중 작은 값을 선택하여 새로운 노드를 생성합니다.
새로운 노드를 결과 연결 리스트에 추가합니다.
작은 값을 선택한 연결 리스트의 노드를 다음 노드로 이동합니다.
위의 과정을 반복하여 두 연결 리스트의 모든 노드를 비교하고 병합합니다.
하나의 연결 리스트가 끝에 도달하면 나머지 연결 리스트의 모든 노드를 결과 리스트에 추가합니다.
결과 연결 리스트를 반환합니다.

SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    SinglyLinkedListNode* ret = nullptr;   // 결과 연결 리스트의 시작을 가리킬 포인터
    SinglyLinkedListNode* current1 = head1; // 첫 번째 연결 리스트를 순회하는 포인터
    SinglyLinkedListNode* current2 = head2; // 두 번째 연결 리스트를 순회하는 포인터
    SinglyLinkedListNode* tail = nullptr;   // 현재 마지막 노드를 추적하는 포인터

    // 두 연결 리스트 중 하나라도 노드가 남아 있는 동안 반복
    while (current1 || current2) {
        SinglyLinkedListNode* newNode = nullptr; // 새로운 노드를 생성할 포인터

        // 두 연결 리스트의 현재 노드를 비교하여 더 작은 값을 선택
        if (current1 && current2) {
            if (current1->data < current2->data) {
                newNode = new SinglyLinkedListNode(current1->data);
                current1 = current1->next; // 첫 번째 연결 리스트의 다음 노드로 이동
            } else {
                newNode = new SinglyLinkedListNode(current2->data);
                current2 = current2->next; // 두 번째 연결 리스트의 다음 노드로 이동
            }
        }
        // 하나의 연결 리스트에만 노드가 남아 있는 경우
        else if (current1) {
            newNode = new SinglyLinkedListNode(current1->data);
            current1 = current1->next; // 첫 번째 연결 리스트의 다음 노드로 이동
        } else if (current2) {
            newNode = new SinglyLinkedListNode(current2->data);
            current2 = current2->next; // 두 번째 연결 리스트의 다음 노드로 이동
        }

        // 결과 연결 리스트에 새로운 노드를 추가
        if (!ret) {
            ret = newNode; // 만약 결과 리스트가 비어 있다면, 새로운 노드를 시작으로 설정
            tail = newNode; // 현재 마지막 노드를 새로운 노드로 설정
        } else {
            tail->next = newNode; // 현재 마지막 노드의 다음 노드로 새로운 노드 연결
            tail = newNode;       // 현재 마지막 노드를 새로운 노드로 업데이트
        }
    }

    return ret; // 병합된 연결 리스트의 시작 포인터를 반환
}