[7. 연결리스트] 7.1 두 개의 정렬된 리스트 합치기

/*
@최종수정 25. 02. 26

• TailNode가 nullptr이 아닌 제대로 마지막 노드를 가리키도록 수정
• 불필요한 AppendNodeEnd 를 제거 하고 마지막 노드부분을 3항연산자가 끝난뒤 실행하도록 변경
• AppendNode의 delete 인한 PrevNode에 쓰레기값이 들어가는 현상 수정
• 리스트를 합친후 PrevNode의 data값은 같은데 메모리주소가 다른점 수정 (더블포인터를 단일 포인터로 변경)
• main에 다른문제에서 사용되는 불필요한 변수들 삭제

*/

 

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

https://msugi.tistory.com/47

[7. 연결리스트] 7.0 연결리스트 기초 작업

연결리스트 문제를 풀기전 LinkedList를 위와 같이 직접 구현했다. 위 LikedList를 이용하여 문제를 풀 예정이다.

---

Q 7.1 두 개의 정렬된 리스트 합치기
단순 연결리스트 2개를 하나의 리스트로 합병하라.

Ex)
L->2->5->7->nullptr
L->3->11->nullptr

=>2->3->5->7->11->nullptr

---

해당 문제의 소스코드와 결과는 다음과 같다.
다음 소스코드에서의 L1 과 L2는 문제의 예시와 다르게 순환하는 구조이다.

// 7.1 두 개의 정렬된 리스트 합치기#include "LinkedList.h"
 
void AppendNode(Node<int>** node, Node<int>** tail)
{
    Node<int>* TempNode = new Node<int>();
    Node<int>* lastNode = new Node<int>();
    *TempNode = **node;
    (*tail)->NextNode = TempNode;
    lastNode = *tail;
    
    
    *tail = TempNode;
    (*tail)->PrevNode = lastNode;
    *node = (*node)->NextNode;
    (*tail)->NextNode = nullptr;
}
List<int>* MergeTwoSortedLists(const List<int>& L1,const List<int>& L2)
{
    List<int>* DummyList = new List<int>();
    Node<int>* DummyHead = new Node<int>();
    Node<int>* tail = DummyHead;
    Node<int>* L1Node = L1.HeadNode;
    Node<int>* L2Node = L2.HeadNode;
 
    int L1cnt = L1.Count;
    int L2cnt = L2.Count;
    int cnt = L1cnt + L2cnt;
    int idx = 1;
    if (cnt == 0) 
    {
        delete DummyHead;
        return nullptr; 
    }
    
    while (!(L1cnt < 0) || !(L2cnt < 0))
    {
        if (idx >= cnt)
        {
            AppendNode(L1cnt > L2cnt ? &L1Node : &L2Node, &tail);
            DummyList->TailNode = tail;
            break;
        }
        if (L1Node->data <= L2Node->data)
        {
            AppendNode(&L1Node, &tail);
            L1cnt--;
        }
        else
        {
            AppendNode(&L2Node, &tail);
            L2cnt--;
        }
        idx++;
    }
 
    DummyList->HeadNode =DummyHead->NextNode;
    DummyList->Count = cnt;
    DummyList->HeadNode->PrevNode = nullptr;
    
    delete DummyHead;
    return DummyList;
}

 

L1 과 L2를 다른부분에서도 사용하고싶어 L3에 메모리를 새로 할당하여 합친 List를 리턴하도록 구현했다.

// mainLinkedList<int> L1,L2,L3;
 
for (int i = 1; i < 10; i++)
{
    if (i % 2 == 0)
    {
        L1.AddNode(L1.list, L1.CreateNode(i));
    }
    else
    {
        L2.AddNode(L2.list, L2.CreateNode(i));
    }
   
}
std::cout << "\n7-1) ";
L1.PrintAllNode(L1.list);
L2.PrintAllNode(L2.list);
 
 
L3.list = MergeTwoSortedLists(*L1.list, *L2.list); //7-1
L3.PrintAllNode(L3.list);
 

결과